放牧代码和思想
专注自然语言处理、机器学习算法

POJ 1284 Primitive Roots 题解《挑战程序设计竞赛》

目录

POJ 1284 Primitive Roots

原根个数:满足{ (xi mod p) | 1 <= i <= p-1 } == { 1, …, p-1 }的x称为模p的原根。给出模p,求原根个数。

4.1更加复杂的数学问题 

模运算的世界 

熟悉初等数论原根的性质的话,一眼就可以看出原根个数等于φ(φ(p)),φ为欧拉函数。证明详见《初等数论及其应用》249页定理9.5:

像我这种数学文盲,是自我扫盲了好久才知道原根原来有这么个性质,稍微看了看证明,似懂非懂。

又因为p是素数,根据定义有φ(p)=p-1,所以最终结果就是求φ(p-1)。

#include <iostream>
using namespace std;

#define MAX_N 65536
int euler[MAX_N];

// O(MAX_N)时间筛出欧拉函数值的表
void init_euler_phi()
{
	for (int i = 0; i < MAX_N; ++i) euler[i] = i;
	for (int i = 2; i < MAX_N; ++i)
	{
		if (euler[i] == i)
		{
			for (int j = i; j < MAX_N; j += i) euler[j] = euler[j] / i * (i - 1);
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	init_euler_phi();
	int p;
	while (~scanf("%d", &p))
	{
		printf("%d\n", euler[p - 1]);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
14052087 hankcs 1284 Accepted 404K 16MS C++ 811B 2015-04-06 00:40:04

关于出题人贾怡@pku,背后有曲折离奇的故事。

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 1284 Primitive Roots 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机