UVA10791
在这里插入图片描述

思路：
由$N=lcm(a,b)=\frac{ab}{gcd(a,b)}$可知，当且仅当$gcd(a,b)=1$时，$a+b$的值最小。因为若$gcd(a,b)>1$，则有:

此时，$\frac{a}{gcd(a,b)}+b<a+b$，结论即证。
那么，目标就变成了将$N$分解为若干素数。
由唯一分解定理：

即N可被唯一分解为若干素数的积。
那么答案是否就是$\sum\limits_{i=1}^{n}(a_ip_i)$了呢？
由$lcm(p,p)=p$可知，若将若干个$a$直接加入集合，那么该集合的$lcm=\sum\limits_{i=1}^{n}p_i\neq N$ 。
那咋办呢？由唯一分解定理，$N=\sum\limits_{i=1}^{n}p_i^{a_i}$，其中由于$p$是素数，所以对于任意的$1\leq i,j\leq n,i\neq j$，有$p_i^{a_i}$与$p_j^{a_j}$互质。
因此答案为：$\sum\limits_{i=1}^{n}(p_i^{a_i})$
一个用于优化的定理：对于正整数$N$，至多只存在一个$N$的素因子$P$，使得$P>\sqrt{N}$。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){

	int Case = 0, n;
	while (cin >> n && n) {
		int Max = ceil(sqrt(n));
		long long Ans = 0;
		int NumberOfDifferentPrimeFactor = 0;
		//枚举素数2到Max
		for (int i = 2; i <= Max; ++i) {
			if (n % i == 0) {
				++NumberOfDifferentPrimeFactor;
				int temp = 1;
				while (n % i == 0) {
					n /= i;
					temp *= i;
				}
				Ans += temp;
			}
		}
		//如果N是素数或1，答案就是1+n
		if (NumberOfDifferentPrimeFactor == 0) {
			Ans = static_cast<long long>(n) + 1;
		}
		//N至少被分解为两个素因子且N至多只存在至多一个大于Max的素因子
		//因此只处理了一个或n>1就要再处理
		else if (NumberOfDifferentPrimeFactor == 1 || n != 1) {
			Ans += n;
		}
		printf("Case %d: %lld\n", ++Case, Ans);
	}

	return 0;

}