POJ 1284 首先说明什么叫a模p的阶？ 《数论概论》中“幂模p与原根”一章中有提到阶的概念： 如果a不被素数p整除，则a模p的阶是指使得 a^e=1（mod p）的最小指数e>=1； 例如2、3、4、5、6模7的阶分别是3、6、3、6、2。  并且本章中给出一些重要的性质，其中有：一个数a模p的阶e总能整除p-1。
那么什么叫原根(primitive root)? 设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。
假设一个数g对于P来说是原根，那么g^i mod P的结果两两不同.

该题题意就是p的元根的个数。 【算法】定理1：如果p有原根，则它恰有φ(φ(p))个不同的原根（无论p是否为素数都适用） {x^i%p | 1 <= i <= p - 1} = {1,2,...,p-1} 等价于       {x^i%(p-1) | 1 <= i <= p - 1} = {0,1,2,...,p-2}, 即为(p-1)的完全剩余系若x,x2...x(p-1)是(p-1)的完全剩余系,根据定理,可以推出若        gcd(x, p-1) = 1时, (1,x,...,x(p-2))也是(p-1)的完全剩余系 因为若x^i != x^j (mod p-1),那么x*x^i != x*x^j (mod p-1), 与条件m矛盾,       所以 x^i = x^j (mod p-1), 由此可以确定答案为Euler(p-1)

#include #include #include #include using namespace std; int euler(int x) { int res = x; for(int i=2;i<(int)sqrt(x*1.0)+1;i++) { if(x%i == 0) { res = res/i*(i-1); while(x%i==0) x/=i; } } if(x>1)res = res/x*(x-1); return res; } int main() { freopen("input.txt","r",stdin); int p; while(scanf("%d",&p)!=EOF) { printf("%d ",euler(p-1)); } return 0; }

POJ 2478 这个题学会了一个类似筛法快速求欧拉函数
#include #include using namespace std; #define N 1000000 #define ll long long ll eular[N+5],prime[N+5],mark[N+5],res[N+5]; void q_eular(){ int i,j; for(i=2;i<=N;++i){ if(mark[i]==0){ prime[++prime[0]]=i; eular[i]=i-1; } for(j=1;j<=prime[0]&&prime[j]*i<=N;++j){ mark[prime[j]*i]=1; if(i%prime[j]==0){ eular[i*prime[j]]=eular[i]*prime[j]; break; } else eular[i*prime[j]]=eular[i]*(prime[j]-1); } } } int main(){ //freopen("input.txt","r",stdin); //freopen("output1.txt","w",stdout); q_eular(); int i,j,n; res[1]=eular[1]; for(i=2;i<=N;++i){ res[i]=eular[i]+res[i-1]; } while(cin>>n&&n){ cout<