[POJ 1284] Primitive Roots （数论，原根）

本文主要是介绍[POJ 1284] Primitive Roots （数论，原根），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

POJ - 1284
题意是，求一个质数的原根
原根的定义是，对于正整数 $a^i mod p (i=[1,p-1])$得到的集合为{1,2,…,p-1}，那么则称 a是 p的一个原根
对于任意正整数 p，其原根个数为 $\phi( \phi(p) )$，$\phi(n)$为欧拉函数，表示小于n且与n互质的数的个数
而质数的欧拉函数值为 p-1，所以其原根个数为 $\phi(p-1)$

#if _WIN32||_WIN64
#define lld I64d
#define llu I64u
#endif
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}const int maxn=1<<16;
int phi[maxn];
void phi_table(){for(int i=1;i<maxn;i++) phi[i]=i;for(int i=2;i<maxn;i++)if(phi[i]==i)for(int j=i;j<maxn;j+=i)phi[j]=phi[j]/i*(i-1);
}int N;int main()
{phi_table();while(~scanf("%d", &N)) printf("%d\n", phi[N-1]);return 0;
}

这篇关于[POJ 1284] Primitive Roots （数论，原根）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---