题解 | #整除问题#

n!=n*(n-1)*(n-2)...*3*2

a^k=a*a*a...*a

1.把2~n进行质因数分解

2.把a进行质因数分解

3.看把2~n分解的质因数里包含多少倍的a的质因数

#include "stdio.h"
#include "string.h"
#include "limits.h"
int isPrime(int n){//质数判定
    if(n<=1){
        return 0;
    }
    for (int i = 2; i*i <=n ; ++i) {
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}
const int MAXN=1000+10;
int A[MAXN];
int P[MAXN];
int Init(){//求质数的筛法
    int index=0;
    memset(A,1,sizeof (int)*MAXN);
    A[0]=A[1]=0;
    for(int i=2;i<MAXN;i++){
        if(!isPrime(i)){
            continue;
        }
        P[index++]=i;
        if(i>MAXN/i){
            continue;
        }
        for(int j=i*i;j<MAXN;j+=i){
            A[j]=0;
        }
    }
    return index;
}
int N_arr[MAXN];
int A_arr[MAXN];
void decompose_N(int n,int p_len){
    for(int i=0;i<p_len;i++){
        int temp=P[i];
        while (n%temp==0){
            N_arr[temp]++;
            n/=temp;
        }
    }
}
void decompose_A(int n,int p_len){
    for(int i=0;i<p_len;i++){
        int temp=P[i];
        while (n%temp==0){
            A_arr[temp]++;
            n/=temp;
        }
    }
}
int main() {
    int n,a;
    int p_len=Init();
    while (scanf("%d%d",&n,&a)!=EOF){
        memset(N_arr,0,sizeof (int)*MAXN);
        memset(A_arr,0,sizeof (int)*MAXN);
        decompose_A(a,p_len);//把a进行质因数分解
        for(int i=2;i<=n;i++){//把2~n进行质因数分解
            decompose_N(i,p_len);
        }
        int k=INT_MAX;
        for(int i=2;i<a;i++){//看把2~n分解的质因数中包含多少(倍的)a的质因数
            if(N_arr[i]!=0&&A_arr[i]!=0){
                if(N_arr[i]/A_arr[i]<k){
                    k=N_arr[i]/A_arr[i];
                }
            }
        }
        printf("%d\n",k);
    }
    return 0;
}