题意：输入正整数n，<注意n=2^31-1是素数。结果是2^31已经超int。用long long，>找至少两个数，使得他们的LCM为n且要输出最小的和；

思路：既然LCM是n，那么一定是n的质因子组成的数，又要使和最小，那么就是ans+=[质因子]^[个数]+...;

之前我一直超时，感觉都无语了。

转载请注明出处：寻找&星空の孩子

题目链接：UVA
10791

也欢迎来我开的专题刷题。

哈哈http://acm.hust.edu.cn/vjudge/contest/view.action?cid=77956#overview

AC代码：

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

using namespace std;

#define LL long long

LL n,sum;

inline LL divisor(LL x)

{

    int t=0,cnt;

    LL tp;

    for(int i=2; i<=sqrt(n); i++)

    {

        cnt=0;

        tp=1;

        if(x%i==0&&i!=n)

        {

            while(x)

            {

                if(x%i==0)

                {

                    cnt++;

                    x=x/i;

                    tp=tp*i;

                }

                else {sum+=tp;break;}

            }

            t++;

        }

        if(!x) break;

    }

    if(x>1){sum+=x;t++;}

 //   printf("sum=%lld\n",sum);

    return t;

}

int main()

{

    int ca=1;

    while(scanf("%lld",&n),n)

    {

        sum=0;

        LL m=divisor(n);

        if(sum==0||m==1)sum=n+1;

        printf("Case %d: %lld\n",ca++,sum);

    }

    return 0;

}

超时代码：

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define LL long long

LL n,sum;

inline LL divisor(LL x)

{

    int t=0,cnt;

    LL tp;

    for(int i=2; i<=x; i++)//这么写，就超时 了。。。。。

    {

        cnt=0;

        tp=1;

        if(x%i==0&&i!=n)

        {

            while(x)

            {

                if(x%i==0)

                {

                    cnt++;

                    x=x/i;

                    tp=tp*i;

                }

                else {sum+=tp;break;}

            }

            t++;

        }

        if(!x) break;

    }

    return t;

}

int main()

{

    int ca=1;

    while(scanf("%lld",&n),n)

    {

        sum=0;

        LL m=divisor(n);

        if(sum==0||m==1)sum=n+1;

        printf("Case %d: %lld\n",ca++,sum);

    }

    return 0;

}