题意
输入正整数n（1 ≤ n ≤ 231 − 1），找至少两个数，使得他们的LCM为n且要输出最小的和（看错题哭唧唧）
分析
唯一分解定理模板。
首先要明确分解出来的两个数一定是互质的，如果不互质，肯定会有更优秀的，毕竟还可以约掉一个gcd，比如4和6不如3和4
因此根据唯一分解定理 N=p1c1 * p2c2 * p3c3 *…… pncn
只要乘起来刚好等于N，这些数其实就是pc，于是答案就是p1c1 + p2c2 + p3c3 +…… pncn
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define RT register
- #define ll long long
- ll k,cas,ans,num;
- void divide(ll n)
- {
- ans=0;num=0;
- ll m=(ll)sqrt((double)n + 10);
- for(RT ll i=2;i<=m;i++)
- {
- if(n%i==0)
- {
- int tmp=1;num++;
- while(n%i==0)
- {
- tmp*=i;
- n/=i;
- }
- ans+=tmp;
- }
- }
- if(num==0)ans=n+1;
- else if(num==1||n!=1)ans+=n;
- }
-
- int main()
- {
- while(scanf("%lld",&k)&&k)
- {
- divide(k);++cas;
- printf("Case %lld: %lld\n",cas,ans);
- }
- }
【UVA10791】最小公倍数的最小和
原文：https://www.cnblogs.com/NSD-email0820/p/9859975.html
