给定两个整数m和n，求最大的k使得m^k是n!的约数
对m质因子分解，然后使用勒让德定理求得n!包含的质数p的阶数，min(b[i] / a[i])即为结果k, 若为0无解
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
const int N = 5008, INF = 0x3F3F3F3F;
#define MS(a, num) memset(a, num, sizeof(a))
#define PB(A) push_back(A)
#define FOR(i, n) for(int i = 0; i < n; i++)
int p[N], a[N], b[N]; int lp(int n, int p){
int ans = 0;
for(int i = p; i <= n; i*= p){
ans += n / i;
}
return ans;
}
int solve(int m, int n){
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
int tot = 0;
for(int i = 2; i * i <= m; i++){
if(m % i == 0){
p[tot] = i;
while(m % i == 0){
a[tot]++;
m /= i;
}
tot++;
}
}
if(m > 1){
p[tot] = m;
a[tot++] = 1;
}
int ans = INF;
for(int i = 0; i < tot; i++){
b[i] = lp(n, p[i]);
if(b[i] < a[i]){
return -1;
}
ans = min(ans, b[i] / a[i]);
}
return ans; }
int main(){
int t, m, n;
cin >>t;
for(int cas = 1; cas <= t; cas++){
scanf("%d %d", &m, &n);
int ans = solve(m, n);
printf("Case %d:\n", cas);
if(ans == -1){
printf("Impossible to divide\n");
}else{
printf("%d\n", ans);
} }
return 0;
}