#include<iostream> #include <strings.h> #include<vector> #include<map> using namespace std; const int MAX = 1001; int main() { //筛选1000以内的全部素数 vector<int> primes; bool isPrime[MAX] ; for (int i = 0; i < MAX; i++) isPrime[i] = true; isPrime[0] = isPrime[1] = false; for (int i = 0; i < MAX; i++) { if (isPrime[i] == true) { primes.push_back(i); for (int j = i * i; j < MAX; j += i) isPrime[j] = false; } } int n, a; while (cin >> n >> a) { map<int, int> n_PrimeNumMap; map<int, int> a_PrimeNumMap; //记录n!各质因子的幂指数 for (int i = 2; i <= n; i++) { int temp = i; int index_prime = 0; while (temp > 1) { int prime = primes[index_prime]; if (temp % prime == 0) { n_PrimeNumMap[prime]++; temp /= prime; } else index_prime++; } } //记录a中各质因子的幂指数 int index_prime = 0; while (a > 1) { int prime = primes[index_prime]; if (a % prime == 0) { a_PrimeNumMap[prime]++; a /= prime; } else index_prime++; } int min = 2147483647; //遍历a的各质因子,求n!中对应质因子幂指数与a的质因子幂指数之比的最小值 for (auto it = a_PrimeNumMap.begin(); it != a_PrimeNumMap.end(); it++) { if (n_PrimeNumMap.find(it->first) == n_PrimeNumMap.end()) {//a中存在n!中不存在的质因子,此时a只能是0次幂 min = 0; break; } if (min > n_PrimeNumMap[it->first] / it->second) { min = n_PrimeNumMap[it->first] / it->second; } } cout << min << endl; } return 0; }// 64 位输出请用 printf("%lld")