题意：
输入n （1<=n<2^31） 求至少两个正整数使得他们的lcm等于n并且他们的和最小，输出最小和
代码：
// a*b=lcm*gcd => a=lcm*gcd/b; a+b=b+lcm*gcd/b 显然gcd越小a+b就越小，即gcd=1，所以几个数 // 互质时他们的和最小。求n的所有的质因子求和。 // 题目要求至少两个数所以要注意n==1和n只有一种质因子的情况。 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; typedef long long ll; ll solve(ll n){ ll nn=n,ans=0; int m=sqrt(n+0.5),cnt=0; for(int i=2;i<=m;i++){ if(n==1) break; if(n%i==0){ cnt++; ll tmp=1; while(n%i==0){ tmp*=i; n/=i; } ans+=tmp; } } if(n>1) ans+=n; if(cnt==1&&n==1) ans++;//只有一种素因子的情况 if(n==nn) ans=n+1;//n是素数的情况 return ans; } int main() { ll n; int cas=0; while(scanf("%lld",&n)==1&&n){ ll ans=solve(n); if(n==1) ans=2; printf("Case %d: %lld ",++cas,ans); } return 0; }