poj 2773 Happy 2006 线性筛

缘起

日常水题 poj 2773 Happy 2006

分析

题意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
如果大公约数（GCD）为1，则两个正整数被认为是相对素数。例如，1,3,5,7,9 ......都是相对于2006年的素数。
现在你的工作很简单：对于给定的整数m，当这些元素按升序排序时，找到相对于m的相对素数的第K个元素。

【输入】
输入包含多个测试用例。 对于每个测试用例，它包含两个整数m（1 <= m <= 1000000），K（1 <= K <= 100000000）。

【输出】
输出第k个和n互质的正整数

【样例输入】
2006 1
2006 2
2006 3

【样例输出】
1
3
5

【限制】
Time Limit: 3000MS
Memory Limit: 65536K

因为 gcd(a,b) = gcd(a+t*b, b), 所以其实 [1,m-1]中和m互质的正整数个数和[m+1, 2m-1]中和m互质的正整数个数是一样的.

所以只需要求出[1,m-1]内和m互质的正整数构成的数组p（恰好是欧拉函数$\phi(m)$个）然后$p[k\%\phi(m)]$ 就是答案 .

而求欧拉函数有两种方法, 一种是基于筛法（【1】），另一种是直接求解法——它基于分解素因数（非大数分解质因数的Pollard rho算法，只是朴素）模板

【1】中已经练习了筛法求欧拉函数，这里使用基于分解素因数的算法.

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
//#include "stdafx.h"

#include <stdio.h>
#include <math.h>
#include <string.h>
//#define LOCAL

int k;

bool sz[1000005];
int p[1000005];

int euler(int m) // 求m的欧拉函数+求出[1,m-1]中与m互质的数+分解素因数了
{
	int ans = m, n = m; // 伊始是m, n保存m原本的值(因为最后要用原本的m)
	for (int i = 2; i<=(int)(sqrt(m*1.0)+0.5);i++) // 加0.5再截断取整防止损失精度（注意, 这里没有使用i*i<=m, 是因为m可能到1e6, i*i可能要用long long,这里不想用）
	{
		if (m%i==0) // i是m的素因子（这里若有需求就可以把m的素因子收集起来）
		{
			for (int j = i; j<n; j+=i)
			{
				sz[j] = false; // 与m不互质了, 特别的, i（是素因子）与m不互质
			}
			ans-=ans/i; // 逐步计算欧拉函数
			while(m%i==0)m/=i; // 直至m没有i这个素因子（这里其实可以打印素因子分解出i的结果）
		}
	}
	if (m>1) // 如果m还剩下的话, 则一定是素因子, 而且是m（未变化之前）唯一的>sqrt(m)的素因子（这种因子显然不能有2个，至多只能有一个）
	{
		for (int j = m; j<n; j+=m)
		{
			sz[j] = false; // 与m不互质了, 特别的, i（是素因子）与m不互质
		}
		ans-=ans/m;
	}
	int top = 0;
	p[0]=0;
	p[++top] = 1; //1 总是与m互质的
	for (int i = 2; i<n; i++)
	{
		if (sz[i]) // 如果i与m互质
		{
			p[++top] = i; // 得到[1,m-1]中与m互质的ans个数（top最后一定等于ans）
		}
	}
	return ans;
}

int main() 
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int m;
	while(~scanf("%d%d",&m,&k))
	{
		memset(sz, true, sizeof(sz)); //预设都是与m互质的
		int e = euler(m); // e是m的欧拉函数的值,即[1,m-1]中与m互质的数的个数
		if (k%e)
		{
			printf("%d\n",k/e*m+p[k%e]);
		}
		else
		{
			printf("%d\n",(k/e-1)*m+p[e]);
		}
	}
	return 0;
}

ac情况

20751832 yfsyfs 2773 Accepted 4432K 32MS G++ 1300B 2019-08-16 16:04:38

参考

【1】https://yfsyfs.github.io/2019/08/11/LightOJ-1370-Bi-shoe-and-Phi-shoe-%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0%E7%BA%BF%E6%80%A7%E7%AD%9B%E6%B3%95/