例10-4 uva10791（唯一分解）-白红宇

例10-4 uva10791（唯一分解）

阅读量：7081 次

发布时间：2019-06-28

本文共 923 字，大约阅读时间需要 3 分钟。

题意：求最小公倍数为n的数的和的最小值。

如12：(3,4),(2,6),(1,12)最小为7

要想a1，a2，a3……an的和最小，要保证他们两两互质，只要存在不互质的两个数，就一定可以近一步优化

只是当n=1时，答案为2，而且可能会超，要用long long /*脑子一抽输出用了I64d，不停wr，好坑

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            using namespace std;typedef long long ll;typedef unsigned long long ull;ll que[1000];ll len;void fin(ll n){ ll m = (ll)sqrt(n+0.5); for(ll i = 2; i <= m && n > 1; i++) { if(n % i == 0) { ll tmp = 1; while(n % i == 0 && n > 1) { n/=i; tmp *= i; } que[len++] = tmp; } } if(n > 1) que[len++] = n;}int main(){ ll n,ans; int cas = 1; while(~scanf("%lld",&n) && n) { printf("Case %d: ",cas++); len = ans = 0; fin(n); if(len == 0 || len == 1) ans = n+1; else { for(int i = 0; i < len; i++) ans += que[i]; } printf("%lld\n",ans); } return 0;}