http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=489
题目大意:
给你正整数n,求最小的x使得2^x mod n = 1。
思路:
n=1无解。任何正数mod 1都为0吧
n为偶数无解,why? 上式可变形为: 2^x=k*n+1,若n为偶数那么k*n+1为奇数,而2^x必为偶数。
n为奇数一定有解,对于乘法逆元:在a mod n的操作下,a存在乘法逆元当且仅当a与n互质。
#include<cstdio> int main() { int n; while(~scanf("%d",&n)) { if( !(n & 1) || n==1) { printf("2^? mod %d = 1\n",n); continue; } int d=1; for(int i=1;;i++) { d*=2; if(d%n==1) { printf("2^%d mod %d = 1\n",i,n); break; } d%=n; } } return 0; }