题目大意
输入整数(n(1le 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 imes a_2)，又由于(a_1>1,a_2>1)，那么(a_1+a_2<a_1 imes 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
",++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
", ++nn, ans);
//最后一行的换行让我很惊讶(UVa什么时候对输出这么随意了?)
return;
}
int main()
{
LL n;
while(scanf("%lld", &n) && n) sol(n);
return 0;
}