zjfc10802^x mod n = 1 Code #include<stdio.h> int process(int i,int n) { long t=2,d=1; while(i){ if(i%2==1) d=d*t%n; t=t*t%n; i/=2; } return d%n; } int main() { int n,i; while(scanf("%d",&n)!=EOF){ if(n%2==0||n==1){ printf("2^? mod %d = 1\n",n); continue;} else{ i=1; while(i){ if(process(i,n)==1){ printf("2^%d mod %d = 1\n",i,n); break; } i++; } } } } 当n为偶数或者1时,x无解 当n为奇数时,有费马小定理可得,取x=n-1 当n为合数时,n=p1*p2*p3... pi为素数。 所以可以取x=(p1-1)*(p2-1)*(p3-1) 同理可得2^x mod n = 1