首页 > 其他 > 详细

唯一分解定理应用

时间:2018-11-17 20:28:37      阅读:145      评论:0      收藏:0      [点我收藏+]

UVA 10791

题意:

输入n,求最少两个数,使得他们的最小公倍数为n,使他们的和最小。

分析:根据唯一分解定理,可以得出  N = p1^n1 * p2^n2 *...* pn^nn

即:当把pi^n1看成整体时和最小。

代码:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
int main()
{
    int t=1;
    ll n;
    while(cin>>n)
    {
        if(!n)
            break;
        printf("Case %d: ",t);
        t++;
        if(n==1)
        {
            printf("2\n");
            continue;
        }
        ll sum=0,ant=0,temp;
        int max_=sqrt(n+1);
        for(int i=2;i<=max_;i++)
        {
            int temp=1;
            if(n%i==0)
            {
                ant++;
                while(n%i==0)
                {
                    temp*=i;
                    n/=i;
                }
                sum+=temp;
            }
           // cout<<temp<<endl;

            if(n==1)
                break;
        }
       // cout<<ant<<endl;
       if(ant==0)
       {
           printf("%lld\n",n+1);
       }
       else if(ant==1||n!=1)
       {
           printf("%lld\n",sum+n);
       }
       else
       {
           printf("%lld\n",sum);
       }
    }
}

 

唯一分解定理应用

原文:https://www.cnblogs.com/linhaitai/p/9975189.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!