首页 > 代码库 > HDU1395 2^x mod n = 1 暴力题
HDU1395 2^x mod n = 1 暴力题
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1395
可以用欧拉定理证明其存在性。
欧拉定理是这样的：
如果a和m互质且a<m,设x为欧拉函数的值，则a^x%m=1
因此在本题中，只要所给的数为奇数，即和2互质，则一定存在解，再暴力就可以了
1 #include<cstdio> 2 int main() 3 { 4 int n; 5 while (scanf("%d", &n) != EOF){ 6 if (n % 2 && n > 2){ 7 int m = 1; 8 for (int i = 1;; i++){ 9 if ((m = m * 2 % n)==1){10 printf("2^%d mod %d = 1\n", i, n);11 break;12 }13 } 14 }15 else16 printf("2^? mod %d = 1\n", n);17 }18 return 0;19 }
HDU1395 2^x mod n = 1 暴力题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。