UVA 10780 Again Prime No Time.(数学)

给定两个整数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;
}