描述
给定 n, k,求一个最大的整数 m,使得 km 是 n! 的约数
输入
第一行两个正整数 n, k
2 ≤ n,k ≤ 109
输出
输出最大的 m
- 样例输入
-
5 2
- 样例输出
-
3
思路:我们知道一个素数在阶乘里的幂次就是一直除就好了。 这题通过率低,是因为直接把K拿来除了,注意这里要是素数才行。
所以我们分解求最小即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ans=;
ll get(int a,int n)
{
ll res=; while(n){
res+=n/a; n/=a;
} return res;
}
int main()
{
int N,K;
scanf("%d%d",&N,&K);
for(int i=;i*i<=K;i++){
if(K%i==){
int num=; while(K%i==) num++,K/=i;
ans=min(ans,get(i,N)/num);
}
}
if(K>) ans=min(ans,get(K,N));
printf("%lld\n",ans);
return ;
}