题目描述

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

输入描述:

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

输出描述:

一个整数.

示例1

输入

6 10

输出

1

解题心得：

首先应注意，n!和a的k次可能数值非常巨大，而不能被int保存。
思路：思考若整数a能整除整数b则它们之间有什么关系？ image.png

若a存在素因数px则b也比存在该素因数，且该素因数在b中对应的幂指数比不小于a中的幂指数
算法： image.png

我们要确定最大的非负整数k，使a中任一素因数的幂指数的k倍依旧小于或等于该素因数在x中对应的幂指数。要求得该k，我们只需一次测试a中每一个素因数，确定b中该素因数对应得幂指数是a中幂指数得几倍，这样所有倍数中最小的那个即为我们要求的k。
对n!分解素因数的方法（p是小于等于n的所有素数）
- 有n/p个整数可以向n!提供一个p因子
- 有n/(pp)个整数可以向n!提供两个p因子，但是它们在之前的步骤中已经提供了一个。所以这里每个再贡献一个。一共贡献n/(pp)个。
- 若n/(p^k)变为0，表示没有整数能提供更多的p因子，关于p的分解结束。
答案错误时，一定要认真检查代码逻辑，可能有些地方实际实现的和想要实现的不一样。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>



int main(){

   int m[1001]={0},n,i,j,size=0,msize[1000],a;
   for(i=2;i<=1000;i++){
        if(m[i]==0){
                msize[size]=i;
                size++;

            if(i>=100)
                continue;
            for(j=i;j*i<=1000;j++){
                m[j*i]=1;
            }
        }
   }


   while(scanf("%d %d",&n,&a)!=EOF){

    int nsize[1000]={0},asize[1000]={0},k,kn;
    for(i=0;i<size;i++){
        if(n/msize[i]==0){
            break;
        }
        k=n/msize[i];
        kn=msize[i];
        while(k){
            nsize[i]+=k;
            kn=kn*msize[i];
            k=n/kn;

        }
        //printf("%d %d\n",msize[i],nsize[i]);
    }



    for(i=0;i<size;i++){
        if(a<=1){
            break;
        }
        while(a%msize[i]==0){
            asize[i]++;
            a=a/msize[i];

        }
    }
    k=1000;
    for(j=0;j<i;j++){
        if(asize[j]){
            kn=nsize[j]/asize[j];

            if(kn<k){
                k=kn;

            }
        }


    }
    printf("%d\n",k);
   }
    return 0;

}