节水网站建设,阿里云建wordpress,光伏发电国家最新政策,上海做营销网站哪个公司好何为原根#xff1f;由费马小定理可知 如果a于p互质 则有a^(p-1)≡1(mod p)对于任意的a是不是一定要到p-1次幂才会出现上述情况呢#xff1f;显然不是#xff0c;当第一次出现a^k≡1(mod p)时#xff0c; 记为ep#xff08;a#xff09;k 当k(p-1)时#xff0c;称a是p的…何为原根由费马小定理可知 如果a于p互质 则有a^(p-1)≡1(mod p)对于任意的a是不是一定要到p-1次幂才会出现上述情况呢显然不是当第一次出现a^k≡1(mod p)时 记为epak 当k(p-1)时称a是p的原根每个素数恰好有f(p-1)个原根f(x)为欧拉函数 定理对于奇素数m, 原根个数为phi(phi(m)), 由于phi(m)m-1, 所以为phi(m-1)。某大牛的证明 {xi%p | 1 i p - 1} {1,2,...,p-1} 等价于 {xi%(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)的完全剩余系 因为若xi ! xj (mod p-1),那么x*xi ! x*xj (mod p-1),与条件m矛盾,所以 xi xj (mod p-1), 由此可以确定答案为EulerPhi(p-1) 代码 #includestdio.h
#define maxn 66666
int euler[maxn1];
int phi(int n)
{int resn;for(int i2;i*in;i){if(n%i0){resres-res/i;while(n%i0)n/i;}}if(n1)resres-res/n;return res;
}
//筛法范围打表 nlogn
void phi()
{for(int i1;imaxn;i)euler[i]i;for(int i2;imaxn;i2)euler[i]/2;for(int i3;imaxn;i){if(euler[i]i) //未被筛到。是素数则用此素数来筛{for(int ji;jmaxn;ji){euler[j]euler[j]/i*(i-1);}}}return ;
}
int main()
{int n;phi();while(scanf(%d,n)!EOF){printf(%d\n,euler[n-1]);}
} 转载于:https://www.cnblogs.com/oneshot/p/3979863.html
