Fork me on GitHub

[UVa-10791 Minimum Sum LCM]

发表于 | 分类于
字数统计: 480字 | 阅读时长 ≈ 2分钟

题面

传送门:UVa-10791
题目大意:给出一个数N,要求出至少两个数以上的正整数,使得

样例

Sample Input
12
10
5
0
Sample Output
Case 1: 7
Case 2: 7
Case 3: 6

思路

还是应用唯一分解定理,不难发现。
对于任何一个质数或者对于一个只有单因子（除去1和它本身）的数，
其数列a只包含1和它本身
此时答案就为n+1.

对于一个合数n,总有

不难发现,当质因数分解时各个质因数的幂之间的gcd必定为1，这样的损耗代价是最小的。

所以求出各个ai和pi就可以gg了。

注意特判,数据范围内是int但是很可能会在计算过程中溢出。

开个long long比较保险。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
typedef long long LL; 
using namespace std;
bool is_prime[56440]; //sqrt(2^31-1) 约等于 56340 
LL prime[56440],pf[56400],cnt = 0,n;
LL kase = 0;
bool check(LL x)
{
	if (x == 1) return 0;
	if (x == 2) return 1;
	for (LL i = 2; i <= sqrt(x+0.5); i++)
		if (x % i == 0) 
		{
			while(x % i == 0) x /= i;
			if (x == 1) return 1;
			else return 0;
		}
	return 1;
}
void Euler_Prime(LL x)
{
	memset(is_prime,1,sizeof(is_prime));
	is_prime[1] = 0;
	for (LL i = 2; i <= x; i++)
	{
		if (is_prime[i]) prime[++cnt] = i;
		for (LL j = 1; j <= cnt && i * prime[j] <= x; j++)
		{
			is_prime[i * prime[j]] = 0;
			if (i % prime[j] == 0) break;
		}
	}
}


int main(int argc, char *argv[])
{
	Euler_Prime(56439);
	while(scanf("%lld",&n) == 1 && n)
	{
		LL ans = 0;
		memset(pf,0,sizeof(pf));
		if (n == 1) 
		{
			printf("Case %lld: 2\n",++kase);
			continue;
		}
		if (check(n))
		{
			printf("Case %lld: %lld\n",++kase,n+1);
			continue;
		}
		for (LL i = 1; i <= cnt; i++)
		{
			if (n % prime[i] == 0) 
			{
				LL ret = 1;
				while(n % prime[i] == 0) n/=prime[i],ret *= prime[i];
				ans += ret;
			}
			if (n == 1) break;
		}
		printf("Case %lld: %lld\n",++kase,ans);
	}
	return 0;
}