前言

长沙市一中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;
}

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

坑点

1. $1$，两个正整数的值是 $1,1$ 所以我们需要输出 $2$。

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;
}