Minimum Sum LCM UVA - 10791——唯一分解定理

我不是女神ヾ 2022-06-15 06:08 175阅读 0赞

Think:  
1知识:唯一分解定理++  
2题意分析:  
1>n == 1的情况和n 是素数的情况  
2>n是单质因子的情况  
3>当n = 2147483647时是一个素数，结果应该输出2147483648，超过int范围，应该思考用long long 来存储  
4>时间复杂度优化问题，如果单纯遍历n，会超时

[唯一分解定理(算术基本定理)百度链接][Link 1]  
[vjudge题目链接][vjudge]  
[建议参考博客链接][Link 2]

以下为Accepted代码

/*
    唯一分解定理:一个正整数等于m个质因子(a1, a2, a3, ..., am)的ki次方(k1, k2, k3, ..., km)的乘积;
    */
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    
    int main(){
        int k, n, m, i, cnt;
        long long sum;
        k = 1;
        while(scanf("%d", &n) && n){
            printf("Case %d: ", k++);
            sum = 0, cnt = 0;
            m = sqrt((double)n);
            for(i = 2; i <= m; i++){
                int v = 1;
                while(n%i == 0){
                    v *= i;
                    n /= i;
                }
                if(v != 1){
                    sum += v;
                    cnt++;
                }
                ///why not judge i is Prime factor ? :Eratosthenes Sieve method Thought
            }
            if(cnt == 0)///n本身作为一个素数||n == 1的情况
                sum = (long long)n + 1;
            else if(n != 1)///余下一个大于sqrt((double)n)的质因子
                sum += n;
            else if(cnt == 1 && n == 1)///单质因子情况
                sum += 1;
            printf("%lld\n", sum);
        }
        return 0;
    }

[Link 1]: http://baike.baidu.com/link?url=RuP0dGNaDTn1qiTWBCqT1smjMebEb3AfVTtIbXfqjGepIDTEQAKhR1ZHL-54CRVACJNgGCfW6S8FM05QVGy0xguh0gX-AwP28Gge_NX8bTsg49UXeSXGwau_dY69TR3SkfzDLLyVE4w_Hcuz5LbrJa
[vjudge]: https://vjudge.net/problem/UVA-10791
[Link 2]: http://blog.csdn.net/goomaple/article/details/8550381