LightOJ-1370 Bi-shoe and Phi-shoe 欧拉函数线性筛法

缘起

最近在学习筛法, 遂找了这道题 LightOJ-1370 Bi-shoe and Phi-shoe

分析

题意很简单

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
给你n个正整数, 对于每个正整数n,找到欧拉函数(x)>=n的最小正整数x, 然后求这些x的和

【输入】
首先是样例数T（<=100）
对于每个样例
首先包含一个正整数 n (<=10000)表示正整数的个数, 然后是n个正整数（<=10^6）

【输出】
对每个样例，输出这些满足条件的最小正整数的和

【样例输入】
3
5
1 2 3 4 5
6
10 11 12 13 14 15
2
1 1

【样例输出】
Case 1: 22 Xukha
Case 2: 88 Xukha
Case 3: 4 Xukha

【hint】
phi(2)=1, phi(3)=2, phi(5)=4>=3, phi(5)=4>=4, phi(7)=6>=5
所以最小花费是 2+3+5+5+7=22

有两种思路

思路1

显然，对于每个x, 就是求满足phi(y)>=x的最小y. 然后求这些y的和. x不超过100w. 我们只需要哈希[1,100w]每个正整数的欧拉函数的值. 然后扫描这n个正整数（这n个正整数先升序排序）.就可以了. 而欧拉函数的线性筛法可以模仿素数的线性筛法. 给出如下ac代码

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
67
68
69
70
71
72
73
74
75
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define LOCAL
typedef long long LL;
using namespace std;

const int maxn = 1e6+5;

bool isprime[maxn]; // isprime为true表示是素数, false表示不是素数

int phi[maxn],n,a[10005]; // 欧拉函数值

void sieve() // 线性筛法
{
	memset(isprime,true, sizeof(isprime)); //预设全部是素数
	for (int i = 0; i<maxn; i++) phi[i] = i; // 预设欧拉函数值为自己
	phi[0] = phi[1] = 0;
	for (int i = 2; i<maxn; i++)
	{
		if (isprime[i])
		{
			for (int j = (i<<1); j<maxn; j+=i)
			{
				isprime[j] = false; // j不是素数
				phi[j]-=phi[j]/i; // 欧拉函数筛法其实就是在素数筛法的时候做点事情而已
			}
		}
	}
	for (int i = 2; i<maxn; i++)
	{
		if (isprime[i]) // 素数的欧拉函数就是自己-1
		{
			phi[i] = i-1;
		}
	}
}

LL solve() // 注意, 这里是long long, 我WA了几次
{
	LL sum = 0, j = 2;
	for (LL i = 0; i<n;i++)
	{
		for (;j<maxn; j++)
		{
			if (a[i]<=phi[j])
			{
				sum+=j;
				break; // 找到了就ok了
			}
		}
	}
	return sum;
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	sieve(); // 先线性处理欧拉函数值
	int t;
	scanf("%d", &t);
	for (int i = 1;i<=t; i++)
	{
		scanf("%d", &n);
		for (int i=0;i<n;scanf("%d", a+i),i++);
		sort(a,a+n); // 升序排序
		printf("Case %d: %lld Xukha\n", i, solve());
	}
	return 0;
}

ac情况

1549681 2019-08-11 20:10:36 1370 - Bi-shoe and Phi-shoe C++ 0.101 6080 Accepted

思路2

其实满足 phi(y)>=x 就是>=x的最小素数. 所以可以写出更加简略的代码(因为不需要phi了)

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
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define LOCAL
typedef long long LL;
using namespace std;

const int maxn = 1e6+5;

bool isprime[maxn]; // isprime为true表示是素数, false表示不是素数

int n,a[10005];

void sieve() // 线性筛法
{
	memset(isprime,true, sizeof(isprime)); //预设全部是素数
	for (int i = 2; i<maxn; i++) if (isprime[i]) for (int j = (i<<1); j<maxn; j+=i) isprime[j] = false; // j不是素数
}

LL solve()
{
	LL sum = 0;
	for (LL i = 0; i<n;i++)
	{
		for (int j = a[i]+1; j<maxn; j++) // >=a[i]的最小素数
		{
			if (isprime[j])
			{
				sum+=j;
				break;
			}
		}
	}
	return sum;
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	sieve();
	int t;
	scanf("%d", &t);
	for (int i = 1;i<=t; i++)
	{
		scanf("%d", &n);
		for (int i=0;i<n;scanf("%d", a+i),i++);
		printf("Case %d: %lld Xukha\n", i, solve());
	}
	return 0;
}

ac情况

1549688 2019-08-11 20:18:37 1370 - Bi-shoe and Phi-shoe C++ 0.042 2172 Accepted