2^x mod n = 1
Time Limit: 1 Second
Memory Limit: 32768 KB
Give a number n, find the minimum x that satisfies 2^x mod n = 1.
Input
One positive integer on each line, the value of n.
Output
If the minimum x exists, print a line with 2^x mod n = 1.
Print 2^? mod n = 1 otherwise.
You should replace x and n with specific numbers.
Sample Input
2 5
Sample Output
2^? mod 2 = 1 2^4 mod 5 = 1
Author: MA, Xiao Source: ZOJ Monthly, February 2003
/*
两个原理：
1.任何奇数都可以被2n-1整除,而偶数则不能.
2.将n1...nx全部相乘后对M取模恒等于n1...nx分别单独对M取模后相乘.
(X * Y) mod K = ((X mod K) * Y) mod K
*/
#include"stdio.h"
#include"time.h"
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
int sum = 1,times = 0;
if((n & 0X1) == 0 || n == 1)
{
printf("2^? mod %d = 1/n",n);
}
else
{
while(1)
{
times++;
sum *= 2;
sum %= n;
if(sum == 1)
break;
}
printf("2^%d mod %d = 1/n",times,n);
}
}
return 0;
}
