Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
字符串算法
图论
数据结构
数论、数学
动态规划
基础算法
计算几何
[其它内容]
科研笔记
归档
标签
SP3713 PROOT - Primitive Root
解题记录
SPOJ
原根
2018-12-19 11:24:41
493
0
0
rockdu
解题记录
SPOJ
原根
题目描述 给你一个质数$p$以及$n$组询问， 判定给定的$r$是否为$p$的原根。 输入输出格式 输入格式 题目有多组测试数据。 每组测试数据的第一行两个正整数$p,n(p<2^{31},1\le n\le 100)$。 以下$n$行， 每行一个数表示这组询问中的$r$。 当$n=p=0$的时候表示输入数据结束， 无需回答。保证数据组数最多60组。 输出格式 对于每组询问， 若$r$是$p$的原根， 输出YES， 否则输出NO。 ``` Input: 5 2 3 4 7 2 3 4 0 0 Output: YES NO YES NO ``` 判原根裸题，考虑如果一个数$g$不是原根，那么存在 $$g^j=1(mod\ p),j<p,j\neq 0$$ 考虑我们知道$g^{p-1}=1(mod\ p)$ 那么一定有$j|p-1$。 直接枚举约数即可。 找原根直接暴力从$1$开始$for$循环一个一个判断就行了。 一般最小的原根在$20$以内。 ``` #include<cstdio> #include<cmath> #define LL long long using namespace std; int n, p, r; LL fpow(LL a, int b) { LL ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p, b >>= 1; } return ans; } void check(int p, int r) { --p; int mx = (int) sqrt(p); if(r == 1 && p != 1) { printf("NO\n"); return; } for(register int i = 2; i <= mx; ++i) { if(p % i != 0) continue; if(fpow(r, i) == 1) { printf("NO\n"); return; } if(fpow(r, p / i) == 1) { printf("NO\n"); return; } } printf("YES\n"); } int main() { while(1) { scanf("%d%d", &p, &n); if(n + p == 0) break; while(n--) { scanf("%d", &r); check(p, r); } } return 0; } ```
上一篇:
BZOJ4244：邮戳拉力赛
下一篇:
BZOJ5104: Fib数列
0
赞
493 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册