---

思路：

整数a可以分解为若干质因数的成绩，如形式：a=p1^x1 p2^x2...

同理，n！也可以分解为如上的形式：n!=p1^y1 p2^y2....（p1,p2为质因数）

则问题可以由a^k和n！的比较转换为两者质因数的比较。

此时k的最大值即为两者质因数的幂次比值的最小值。

 

细节：求质因数幂次的方法：

void GetPrime(vector<int> &factor,int num)
{
    for(int i=2;i*i<=num;i++)//统计所有小于sqrt(num)的素因数的个数
    {
        while(num%i==0)
        {
            factor[i]++;
            num/=i;

            if(num<=1) return;
        }

    }

    if(num>1) factor[num]++;//存在一个大于sqrt(num)的素因数

    return;
}

 

细节2：如何求n！的质因数：从2~n依次调用GetPrime即可

 

细节3：

for(int i=2;i<=a;i++)
            if(factor_a[i]) k=min(k,factor_n[i]/factor_a[i]);

此处枚举的范围是到a，是因为a的所有质因数中最大（如果存在）即为a自己。

 

当a的质因数存在时，比较n！的质因数幂次和a的质因数幂次，取最小值即为k（若>k的话则a^k的质因数不能被n！覆盖，此时n!无法被a^k整除）

 

 

C++代码：

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e3+10;
int n,a...