poj 3421 X-factor Chains-白红宇

poj 3421 X-factor Chains

阅读量：6246 次

发布时间：2019-06-22

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

给定一个数X.

1=X0, X1, X2.....Xm = X 是X的因数

求一串因数,要求Xi | Xi+1,即上一个因数能整除下一个因数,

问这条串就的最长长度,和有多少条这样长度的串.

X = p1^a1 * p2^a2 ... pn^an

Xi = p1^b2 * p2^b2 ...pk^bk... pn^bn,

Xi+1 = p1^b2 * p2^b2 ...pk^(bk)... pn^bn,

要使length最长,只要从1开始，每次只乘以X的一个质因数即可,即length = (a1+a2+...an)

而方法数就是X的质因数的重排列数,way = (a1+a2+...an)!/(a1!a2!...an!)

View Code

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #define LL long longusing namespace std;int prime[90000],cnt=0;bool hash[550024]={ 0};void Prime( ){ int t1 = 1 << 10,t2=1<<20; for( int i = 3 ; i <= t1; i += 2 ) { if( !hash[i>>1] ) { int x = i << 1; for( int j = i * i ; j <= t2 ; j += x ) hash[j>>1] = true; } } prime[cnt++] = 2; t1 = 1 << 19; for( int i = 1 ; i <= t1; i ++ ) { if( !hash[i] ) { prime[cnt++] = i<<1|1; } }}LL A( int n ){ LL ans = 1; while( n ) { ans *= n; n--; } return ans; }void Solve( int n ){ int num[24]={ 0},count=0,len=0; for( int i = 0; i < cnt; i ++ ) { if( prime[i] > n ) break; if( n % prime[i] == 0 ) { while( n % prime[i] == 0 ) { num[count]++; n /= prime[i]; } len += num[count]; count++; } } LL ans = A( len ); for( int i = 0 ; i < count ; i ++ ) ans /= A( num[i] ); printf( "%d %I64d\n",len,ans ); }int main( ){ int n; Prime(); while( scanf( "%d",&n )==1 ) { Solve( n ); } //system( "pause" ); return 0;}