poj1284(欧拉函数+原根)
题目链接:https://vjudge.net/problem/POJ-1284
题意:给定奇素数p,求x的个数,x为满足{(xi mod p)|1<=i<=p-1}={1,2,...,p-1}。
思路:题目的实质就是问p有多少原根。
下面是百度对原根的解释:
设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根。(其中φ(m)表示m的欧拉函数)
假设一个数g是P的原根,那么g^i mod P的结果两两不同,且有 1<g<P, 0<i<P,归根到底就是g^(P-1) = 1 (mod P)当且仅当指数为P-1的时候成立.(这里P是素数).
简单来说,g^i mod p ≠ g^j mod p (p为素数)//这句话就是满足的条件。
其中i≠j且i, j介于1至(p-1)之间
这个题目就是将原根的定义解释了一遍。
有两点重要的原根性质
1. 模m有原根的充要条件是m= 1,2,4,p,2p,p^n,其中p是奇质数,n是任意正整数。
2. 当模m有原根时,它有φ(φ(m))个原根。
某大牛的证明(没看懂...QAQ):
{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),
由此可以确定答案为eu(p-1)。
知道答案是eu(p-1),代码就很好实现了,筛法打表65525以内的数的欧拉函数即可。
AC代码:
#include<cstdio>
using namespace std; int eu[],p; void eular(){
for(int i=;i<=;++i)
if(!eu[i])
for(int j=i;j<=;j+=i){
if(!eu[j]) eu[j]=j;
eu[j]=eu[j]/i*(i-);
}
} int main(){
eular();
while(~scanf("%d",&p)){
printf("%d\n",eu[p-]);
}
return ;
}
最新文章
- ios中自定义tableView,CollectionView的cell什么时候用nib加载,什么时候用标识重用
- json数据转换失败json_last_error int(4)
- mybatis配置问题
- 《android基于andFix的热修复方案》思路篇
- 分享Windows Server 2012 R2的获取正版密钥方法
- 使用RPM管理软件包
- 设计包含min函数的栈
- 摄像机(CCCamera)
- .Net设计模式_原型模式
- safari 在 iPad Portrait 模式默认设置980px宽度
- 在 Less 中写 IE 的css hack
- MyDAL - 引用类型对象 .DeepClone() 深度克隆[深度复制] 工具 使用
- throw与throws
- form的submit()方法不能触发onsubmit事件的解决方法,兼容各版本浏览器。
- SpringMVC 集成Log4j
- Hive原理总结(完整版)
- jmap -histo pid 输出的[C [B [I [S 的含义
- thinkphp在linux下报mkdir()错误
- Java05-Java基础语法(四)循环结构
- Django时间时区问题(received a naive datetime while time zone support is active)
热门文章
- 学到了林海峰,武沛齐讲的Day51 django+数据库
- sql DATEDIFF函数使用
- luogu 2993 [FJOI2014]最短路径树问题 Dijkstra+点分治
- CF 672C 两个人捡瓶子 最短路与次短路思想
- Codeforces 482E ELCA (LCT)
- Android_(游戏)打飞机03:控制玩家飞机
- 出现org.maven.ide.eclipse.MAVEN2_CLASSPATH_CONTAINER, 且出现无法找到Maven的依赖的问题
- 191016Django基础
- Hive SQL 语法学习与实践
- win10上的docker怎么设置开机不要自动启动 [问题点数:20分,结帖人xyq1986]