原根个数:满足{ (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 题解《挑战程序设计竞赛》