UVa10791 - Minimum Sum LCM （分解因数）

Love The Way You Lie 2022-06-08 10:09 143阅读 0赞

输入n，求两个正整数，是他们的最小公倍数为n，并且是其中最小的一组，输出他们的和。

**唯一分解定理** n=ap1 \* bp2 \* cp3……  
**任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积**

例如 36 = 2 \* 2 \* 3 \* 3  
如果两个数最小公倍数是36，那么这两个数必须互质，像6 \* 6就是不符合规定的，因为最小公倍数为6，那么我们把相同的因数组合，这样的话就一定是互质的了。  
2\*2 和 3\*3  
有了这个思想，我们需要一个for循环遍历一下因数，把相同的因数提取，直到n√  
这里还有个坑，就是如果n是一个质数的话，或者是个1，要另外判定。

#include<iostream>
    #include<cmath>
    #define MAXN 1000
    #define ll long long
    
    using namespace std;
    
    ll a[MAXN];
    ll kase; 
    
    void disassembly(ll n) {    
        kase = 0;
        ll index = (ll)sqrt(n + 0.5);
        for(ll i = 2; i <= index; i++) {
            if(!(n%i)) {
       //如果是因数的话就进入
                ll vis = 1;
                while(!(n%i)) {
       //把所有能提取的因数i全部提取
                    vis *= i;
                    n /= i;
                }
                a[kase++] = vis;//放进一个数组里
            }
        }
        if(n > 1) a[kase++] = n;//把剩下的质数加上，可能是本身，可能是别的质数
    }
    
    int main () {
        ll n, q = 0;
        while(cin >> n && n) {
            disassembly(n);
            ll ans = 0;
            if(!kase || kase == 1) {
       //如果是1的话，和是质数的时候答案是一样的
                ans = n + 1; 
            }else {
                for(ll i = 0; i < kase; i++) {
                    ans += a[i];
                }
            }
            printf("Case %lld: %lld\n", ++q, ans);
        }
        return 0;
    }