洛谷P1069 细胞分裂

数学

质因数分解

题意 求一个最小的 自然数 x 使 s[ i ]^x 任意一个s[ i ] 能够整除以 m1^m2 只要能够整除以就行

题解 这题就是分解质因数 但是 分解s[ i ] 就太大了，我们只要分解 m1 就行了 ，因为m1比较小，分解完之后指数乘 m2就行

然后看s[ i ] 是否含有 m1的质因子 ，有就分解，如果没有这个质因子，说明一定不行，直接退出，有的话就是

m1 中含有的这个因子的个数 除以 s[ i ] 中含有的这个因子的个数，然后向上取整

PS m1==1 时特判一下， 0 步到位

还有分解质因数如果质数就会剩下一个数 ，这个数的个数也要乘以 m2

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 using namespace std ; 10 11 struct node{12 int val,num,oth ; 13 };14 const int inf = 2e9 ; 15 int m1,m2,n,tot,x,mi,mx,k,kk ; 16 node s[1001] ; 17 18 inline int read() 19 {20 char ch = getchar() ; 21 int x = 0,f = 1 ; 22 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 23 while(ch>='0'&&ch<='9' ) { x = x*10 + ch - 48 ; ch = getchar() ; } 24 return x*f ; 25 }26 27 int main() 28 {29 n = read() ; 30 m1 = read() ; m2 = read() ; 31 tot = 0 ; 32 if (m1==1) {cout<<0<