题目1104：整除问题

﹏ヽ暗。殇╰゛Y 2021-11-02 14:22 356阅读 0赞

**题目描述：**

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

**输入：**

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

算法：

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #include<vector>
    #include<string>
    #include<math.h>
    #include<map>
    #include<set>
    #include<algorithm>
    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;  
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/08/21/2649558.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/8886df5b692d46efa79761ae956dcf6d.png