2^x mod n = 1

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9534 Accepted Submission(s): 2932

Problem Description

Give a number n, find the minimum x(x>0) 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

Recommend

Ignatius.L

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int n,ans,s;
 5     while(scanf("%d",&n)!=EOF)
 6     {
 7         if(n%2==0||n==1)
 8             printf("2^? mod %d = 1
",n);
 9         else
10         {
11             ans=1;s=2;
12             while(s!=1)
13             {
14                 ans++;
15                 s=s*2%n;//取余。。。
16             }
17             printf("2^%d mod %d = 1
",ans,n);
18         }
19     }
20     return 0;
21 }