#include <map> #include <string> #include <iostream> #include <cctype> #include <stack> #include <vector> using namespace std; //判断x是不是质数 bool isprime(int x) { if (x == 2) return true; for (int i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true; } int main() { //注意:质因数我们不考虑1 int n, a; while (cin >> n >> a) { vector<int>aa(1000, 0);//存储a的质因数 aa[i]代表质因数i有aa[i]个 vector<int>nn(1000, 0);//存储n的阶乘的所有质因数 //求解a的质因数 int tt = a; for (int i = 2; i * i <= a; i++) { if (isprime(i)) while (tt % i == 0) { aa[i]++; tt /= i; } } //注意要检查一下最后的t是不是1,如果不是1,一定是一个质数,后面判断其实可以省略 //举个例子 将26分解 2*13,tt=13,13还没被检测出来就跳出循环了,所以循环出来要判断一下 //相反,如果是12,分解为2*2*3,出来的时候tt是1,所以不必处理 if (tt != 1 && isprime(tt)) aa[tt]++; //求解2~n的质因数 ---与求解a的质因数类似,只是需要求解2到n每一个数的质因数,进行叠加 for (int j = 2; j <= n; j++) { int t = j; for (int i = 2; i * i <= j; i++) { if (isprime(i)) while (t % i == 0) { nn[i]++; t /= i; if (t == i) break;//如果最后分解的结果是两个质数相乘,跳出即可 } } if (t != 1 && isprime(t)) nn[t]++; } int k = 0; //举个例子 a是2*5 n!=2*3*4**5*6=2*3*2*2*5*2*3 //我们尝试去遍历a的每一个质因子,然后看看n!对应的质因子数目是a的多少倍,k就是其中的最小值,类似于短板效应 //比如a有一个质因子2,一个质因子5,而n!虽然有4个质因子2,却只有一个质因子5,显然k应取决于质因子5的倍数关系,k至少也是0,所以初始化为0 for (int i = 0; i < 1000; i++) { if (aa[i] > 0) { if (k == 0) k = nn[i] / aa[i]; else k = min(nn[i] / aa[i], k); } } cout << k << endl; } } // 64 位输出请用 printf("%lld")