题目大意
输入整数\(n(1\le n<2^{31})\) ，求至少两个正整数，是它们的最小公倍数为$ n$，且这些整数的和最小。输出最小的和。
有多组测试输入，以\(0\)结束。
题解
首先，我们把问题简化：输入正整数\(n\)，求几个正整数（可以是一个），是它们的最小公倍数为\(n\)，且这些整数的和最小。输出最小的和。
我们考虑\(n\)是素数时，不难证明只有一个数\(n\)，那么如果要求至少要分解成两个，那么只能在加一个\(1\)。
当\(n\)是合数时。如果\(n\)能被分解为两个大于\(1\)的互质整数的积\(a_1,a_2\)，由于\((a_1,a_2)=1\)，如\([a_1,a_2]=a_1\times a_2\)，又由于\(a_1>1,a_2>1\)，那么\(a_1+a_2<a_1\times a_2\)，所以我们要把它分解开来。这样，我们就把问题转成了上面简化问题中\(n=a_1,n=a_2\)的子问题。如此递归下去，我们发现：设\(n\)的标准分解式为\(n=p_{1}^{a_1}p_{2}^{a_2}\cdots p_x^{a_x}\)，当所有数分别为\(p_{x_0}^{a_{x_0}}\)时最小。
此外，我们还要特判一下开始\(n=p^a\)的情况。此时\(n\)无法继续分解，则\(ans=n+1\)。最后，记得当\(n=1\)时，\(ans=2\)。
然后我们来看实现问题。
从\(1\)枚举到\(n\)？TLE。
是否记得判断一个数是素数的时候（在学会Miller-Rabin之前）我们通常是从\(1\)枚举到\(\sqrt{n}\)，这题可以吗？
我们发现对于任意正整数\(n\)，在超过\(\sqrt{n}\)且不等于\(n\)的数中，最多只有一个。如果有两个，那么它们的乘积就已经超过\(n\)了。那么我们就只要枚举\(\sqrt{n}\)个数即可。
代码
#include <cstdio>
typedef long long LL;
int nn;
inline void sol(LL n)
{
int f=0;
LL ans=0;
if(n==1)//对1的特判
{
printf("Case %d: 2\n",++nn);
return;
}
LL ttt,tn=n;
for(LL i=2; i*i<=n; ++i)//计算标准分解式，枚举到sqrt即可
{
ttt=1;
if(!(n%i) && (n!=1))
{
do
{
ttt*=i;
n/=i;
}
while(!(n%i) && (n!=1));
f++,ans+=ttt;
}
if(n==1) break;
}
if(tn==n || f==1) ans++;
//tn==n:n是素数，f==1:n不是素数但除1与n外的因子只有一个
if(n!=1) ans+=n;//在sqrt(n)以上除n外还有一个n的因子
printf("Case %d: %lld\n", ++nn, ans);
//最后一行的换行让我很惊讶(UVa什么时候对输出这么随意了?)
return;
}
int main()
{
LL n;
while(scanf("%lld", &n) && n) sol(n);
return 0;
}