poj 3421 X-factor Chains 素数筛选因子分解-白红宇

poj 3421 X-factor Chains 素数筛选因子分解

阅读量：4113 次

发布时间：2019-05-25

本文共 1999 字，大约阅读时间需要 6 分钟。

题意：要你构造一个序列x0,x1,x2,,,,xk其中x0=1，xk=n(一个输入的值)，序列满足xi<xi+1且xi整除xi+1,求

输入n后,满足该要求的最长的序列，并有多少条这样的最长序列；；

#include 
    
      #include
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include
            #include 
            
              #include 
             
               using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int maxn = (1<<20)+5; int pri[maxn],v[maxn]; ll fact[1000]; void prime() { memset(v, 0, sizeof(v)); memset(fact,0,sizeof(fact)); int p = 0; for (int i = 2; i <= maxn;i++) if (!v[i]) { pri[++p] = i; for (int j = i; j <= maxn; j += i) v[j] = 1; } } ll factor(int n) { if(fact[n]) return fact[n]; ll res=1; for (int i = 1; i <= n; i++) { res *= i; fact[i]=res; } return fact[n]; } int main() { prime(); int n; while (~scanf("%d", &n)) { int temp = n;ll fenzi = 0, fenmu = 1,maxl=0; for (int i = 1; temp > 1;i++) if(temp%pri[i] == 0) { int cnt = 0; while (temp%pri[i] == 0) { cnt++; temp /= pri[i]; maxl++; } fenmu *= factor(cnt); } fenzi = factor(maxl); printf("%lld %lld\n",maxl,fenzi/fenmu); } return 0; }

分析：将n分解成素数因子乘积的形式，再素数因子指数排列组合一下；

易错点：2^20，以后就写成1<<20；；还要注意提前打好素数表；暴力肯定超时

wa代码：

#include 
     
       #include
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; int main() { int n; while (~scanf("%d", &n)) { int num=1, maxl = 1; for (int i = 2; i <= n-1 ; i++) { int cnt=1,last; if (n % i == 0) { last = i; for (int j = i; j <= n -1; j += i) if (n%j == 0&&j%last==0) { cnt++; last = j; } } if (cnt > maxl) { num = 1; maxl = cnt; } else if (cnt == maxl) num++; } printf("%d %d\n", maxl, num); } return 0; }