【题解】UVa 10791【Minimum Sum LCM】

分析

这里使用算术基本定理,不难发现分解质因数后把所有的因数及其幂和加起来就是答案,不过需要注意质数和$1$的情况,以及不要溢出了。

代码

#include<cstdio>
#include<cmath>
#include<cstring>
typedef long long int64;
const int MAXN = 666;
int p[MAXN],c[MAXN];
int64 ans;
int divide(int n){
    int64 m = 0;
    for(int i = 2;i <= sqrt(n);i++){
        if(n % i == 0){
            p[++m] = i,c[m] = 0;
            while(n % i == 0) n /= i,c[m]++;
        }
    }
    for(int i = 1;i <= m;i++) ans += pow(p[i],c[i]);
    if(n > 1) p[++m] = n,c[m] = 1,ans += n;
    if(m == 1) ans += 1;
    return m;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,id = 1;
    while(scanf("%d",&n) == 1 && n){
        if(n == 1){printf("Case %d: 2\n",id++);continue;}
        memset(p,0,sizeof(p));memset(c,0,sizeof(c));
        ans = 0;
        int m = divide(n);
        printf("Case %d: %lld\n",id++,ans);
    }

    return 0;
}

Hints

$uDebug$是个好网站,对于$UVa$的题来说,都可以查错