UVA10791 最小公倍数的最小和 Minimum Sum LCM 题解

· · 题解

前言

长沙市一中8机房0714模拟测1。

传送门

blog

思路

本题思路，首先我们先看 \operatorname{lcm}，明显要使得这些数的 \operatorname{lcm} = n 那么我们就需要所有的数的质因子必须包含 n 的质因子。

若 1 \le a,b，则 a\times b \ge a+b，所以我们就有了策略。

将同一个质因子放在一个数中，这样就可以使得数最小。

for(ll i = 2;i <= sqrt(b);++i){
    ll sum = 1;
    while(b % i == 0){
        sum *= i;
        b /= i;
    }
    if(sum != 1)ans += sum;
}

这样就保证了每个质因数在同一个数中。

坑点

  2. 质数，值为 1,n 我们应该输出 1 + n。

  3. 质数的指数幂，值为 n,1，输出 1 + n。

  4. 输出 ans。

AC Code


#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll b;

int main(){
    int cnt = 0;
    while(1){
        cnt++;
        cin>>b;
        if(b == 0)break;
        if(b == 1){
            cout<<"Case "<<cnt<<": "<<2<<endl;
            continue;
        }
        ll ans = 0,can = 0;
        for(ll i = 2;i <= sqrt(b);++i){
            ll sum = 1;
            while(b % i == 0){
                sum *= i;
                b /= i;
            }
            if(sum != 1)ans += sum,can++;
        }
        if(b > 1)ans += b,can++;
        if(can < 2)cout<<"Case "<<cnt<<": "<<ans + 1;
        else cout<<"Case "<<cnt<<": "<<ans;
        cout<<endl;
    }
    return 0;
}