poj 1284 Primitive Roots (原根)
2024-08-25 05:23:55
Primitive Roots
Time Limit: 1000MS | Memory Limit: 10000K | |
Description
We say that integer x, 0 < x < p, is a primitive root modulo odd prime p if and only if the set { (xi mod p) | 1 <= i <= p-1 } is equal to { 1, ..., p-1 }. For example, the consecutive powers of 3 modulo 7 are 3, 2, 6, 4, 5, 1, and thus 3 is a primitive root modulo 7.
Write a program which given any odd prime 3 <= p < 65536 outputs the number of primitive roots modulo p.
Write a program which given any odd prime 3 <= p < 65536 outputs the number of primitive roots modulo p.
Input
Each line of the input contains an odd prime numbers p. Input is terminated by the end-of-file seperator.
Output
For each p, print a single number that gives the number of primitive roots in a single line.
Sample Input
23
31
79
Sample Output
10
8
24
Source
题意:求奇素数的原根的个数
奇素数p的原根个数=φ(p-1)
证明不会,粘的题解
对于给出的素数p,
首先要明确一点:p的元根必然是存在的(这一点已由Euler证明,此处不再赘述),因此,不妨设其中的一个元根是a0(1<=a0<=p-1)
按照题目的定义,a0^i(1<=i<=p-1) mod p的值是各不相同的,再由p是素数,联系Fermat小定理可知:q^(p-1) mod p=1;(1<=q<=p-1)(这个在下面有用)
下面证明,如果b是p的一个异于a的元根,不妨令b与a0^t关于p同余,那么必然有gcd(t,p-1)=1,亦即t与p-1互质;反之亦然;
证明:
若d=gcd(t,p-1)>1,令t=k1*d,p-1=k2*d,则由Fermat可知
(a0^(k1*d))^k2 mod p=(a0^(k2*d))^(k1) mod p=(a0^(p-1))^(k1) mod p=1
再由b=a0^t (mod p),结合上面的式子可知:
(a0^(k1*d))^k2 mod n=b^k2 mod p=1;
然而b^0 mod p=1,所以b^0=b^k2 (mod p),所以b^i mod p的循环节=k2<p-1,因此这样的b不是元根; 再证,若d=gcd(t,p-1)=1,即t与p-1互质,那么b必然是元根;
否则假设存在1<=j<i<=p-1,使得b^j=b^i (mod p),即a0^(j*t)=a0^(i*t) (mod p),由a0是元根,即a0的循环节长度是(p-1)可知,(p-1) | (i*t-j*t)->(p-1) | t*(i-j),由于p与
t互质,所以(p-1) | (i-j),但是根据假设,0<i-j<p-1,得出矛盾,结论得证; 由上面的两个证明可知b=a0^t (mod p),是一个元根的充要条件是t与p-1互质,所有的这些t的总个数就是Phi(p-1);
#include<cstdio>
#define N 65537
using namespace std;
int v[N],prime[N],phi[N],cnt,n;
void euler()
{
phi[]=;
for(int i=;i<=N;i++)
{
if(!v[i])
{
v[i]=true;
prime[++cnt]=i;
phi[i]=i-;
}
for(int j=;j<=cnt;j++)
{
if(i*prime[j]>N) break;
v[i*prime[j]]=true;
if(i%prime[j]==)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-);
}
}
}
int main()
{
euler();
while(scanf("%d",&n)!=EOF) printf("%d\n",phi[n-]);
}
最新文章
- U盘安装WIN10专业版
- DateTime的精度小问题
- SQL AND &; OR 运算符
- (原创) cocos2dx使用Curl连接网络(客户端)
- Okhttp https
- 用VisualC++建立SOAP客户端应用(一)
- YII页面跳转
- SharePoint 2013 新功能探索 之 SPGroup、SPUser 事件处理程序 还要继续改进
- ios基础篇(九)——自定义UITabBar
- WPF passwordbox 圆角制作
- jdk1.5 jdk1.6 jdk1.7 jdk1.8 下载地址
- UIView的一些常用属性和方法
- ##DAY15——UICollectionView
- C#基础知识——类的继承
- VNC VIEWER的使用集锦
- mimtproxy和arpspoof实现局域网MITM
- 2017";百度之星";程序设计大赛 - 资格赛【1001 Floyd求最小环 1002 歪解(并查集),1003 完全背包 1004 01背包 1005 打表找规律+卡特兰数】
- 修改WordPress后台默认登陆地址提高网站安全性
- PAT (Basic Level) Practice (中文)1022 D进制的A+B
- Centos下安装软件的常用方法
热门文章
- arcgis 10.3中文版安装教程、配置及常见问题(百度的有些错误)
- Codeforces Round #341 (Div. 2) E. Wet Shark and Blocks dp+矩阵加速
- 如何在mvc项目中使用apiController
- rpm安装和二进制安装
- 1014 C语言文法定义与C程序的推导过程
- Internet History, Technology and Security (Week 1)
- ubuntu下安装vsftpd及vsftpd配置文件不见的解决办法
- CentOS7无法使用tab补全功能??
- 使用 Idea 打 scala程序的 jar 包 - 02
- 利用userData实现客户端保存表单数据