题目1104：整除问题-白红宇

题目1104：整除问题

阅读量：5234 次

发布时间：2019-06-14

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

题目描述：

给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。

输入：

两个整数n(2<=n<=1000)，a(2<=a<=1000)

算法：

分解N！和 a 的因子...是否整除就看因子是否包含。。

View Code

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  using namespace std;int n, a, cnt;int prime[1100];int hash[1100]={ 0};int visit[1100];void Get_Prime( ){ cnt = 0; for( int i = 2; i <= 35; i++) { if( !hash[i] ) { for( int j = i + i; j <= 1000; j += i ) hash[j] = 1; } } for( int i = 2; i <= 1000; i++) if( !hash[i] ) prime[cnt++] = i; }void Get_Fac( int x, int *array){ int id = 0; while( x ) { while( x % prime[id] == 0 && x!= 1) x /= prime[id], array[prime[id]]++; id++; if( x == 1) break; } } void solve( ){ int ans = 0x7f7f7f7f; for( int i = 0; i < 1000; i++) { if ( hash[i] && visit[i] ) { if( hash[i] >= visit[i] ) { ans = min(ans, hash[i] / visit[i]); } else { ans = 0; break; } } else if( !hash[i] && visit[i] ) { ans = 0; break; } } printf("%d\n",ans); }int main( ){ Get_Prime( ); while( scanf("%d%d",&n,&a) != EOF) { memset(hash,0,sizeof(hash)); memset(visit,0,sizeof(visit)); for( int i = 2; i <= n; i++) Get_Fac( i, hash); Get_Fac(a, visit); solve( ); } return 0; }