且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

UVA 10791

更新时间:2022-08-13 08:40:21

题目链接:https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1732
hint:素因子分解

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
int main()
{
    int m,ss,flag,cnt;
    int cas=1;
    while(scanf("%d",&m),m)
    {
        LL ans=0;
        ss=(int)sqrt((double)m+0.5);//不要ss=吗;
        flag=0;
        for(int i=2; i<=ss; i++)//注意这里千万不要i*i<=ss啊!!!
        {
            if(m % i == 0)
            {
                flag++;
                cnt=1;
                while(m % i == 0)
                {
                    cnt*=i;
                    m/=i;
                }
                ans+=cnt;
            }
        }
        if(flag == 0)
            ans=(LL)m+1;
        else if(m>1 || flag == 1)
            ans+=m;
        printf("Case %d: %lld\n",cas++,ans);
    }
    return 0;
}