题解：ABC280D - Factorial and Multiple

·题目

链接：Atcoder。

链接：洛谷。

·难度

算法难度：B。

思维难度：A。

调码难度：A。

综合评价：普及/提高-。

·算法

质因数分解+数论。

·思路

这题真是的，纯纯考数学。

首先，如果k本身是质数输出k即可（前面乘几都没用）。

剩下的答案，先给k分解质因数，记每个质数为p[i]，对应的个数为sum[i]，质数数量为cnt，最差情况下答案为p[cnt]*sum[cnt]，这里阶乘中至少有sum[cnt]个p[cnt]的倍数，自然满足要求。于是我们先从1枚举到根号k，如果之中没有合法的情况就输出最差情况下的答案。

·代价

O(sqrt(k))。

·细节

判断是否合法，可以用sumot[i]记录当前的阶乘中能够整除p[i]的多少幂次。

最后判断是否是每个sum[i]都<=sumot[i]即可。

·代码

#include<bits/stdc++.h>
#define S 1100000
using namespace std;
long long p[S]={},sum[S]={},sumot[S]={},cnt=0,k=0;
bool prime(long long num);
void resolve(long long num);
int main(){scanf("%lld",&k);if(prime(k)==true){printf("%lld\n",k);return 0;}resolve(k);for(long long i=1;i*i<=k;i++){long long tmp=i;bool flag=false;for(long long j=1;j<=cnt;j++){while(tmp%p[j]==0){tmp/=p[j];sumot[j]++;}if(sum[j]>sumot[j]){flag=true;}}if(flag==false){printf("%lld\n",i);return 0;}}long long ans=p[cnt]*sum[cnt];printf("%lld\n",ans);return 0;
}
bool prime(long long num){for(long long i=2;i*i<=num;i++){if(num%i==0){return false;}}return true;
}
void resolve(long long num){long long tmp=num;for(long long i=2;i*i<=num;i++){if(tmp%i==0){cnt++;p[cnt]=i;}while(tmp%i==0){tmp/=i;sum[cnt]++;}}if(tmp>1){if(p[cnt]==tmp){sum[cnt]++;}else{cnt++;p[cnt]=tmp;sum[cnt]++;}}return;
}