2^x mod n = 1

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

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.

思路：

1. 当n为偶数时，bn + 1（b为整数）是奇数，而2^x是偶数，故 2^x mod n = 1不可能成立；

2. 当n等于1时，不能成立

3. 当n为非1的奇数时，n和2互质，由欧拉定理：若a，n为正整数，且两者互素，则a^phi(n) mod n = 1，其中phi(n)是n的欧拉函数。知2^phi(n) mod n = 1.因此phi(n)必是符合要求的x，但phi(n)未必是最小的，遍历小于其的正整数，逐一试验即可，计算2^x mod n时用快速幂乘。

AC Code：

 #include <iostream>

 #include <vector>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 //计算n的欧拉函数

 int Eular(int n)

 {

     int res = , i;

     for (i = ; i * i <= n; i++){

         if (n % i == ){

             n /= i;

             res *= (i - );

             while (n % i == ){

                 n /= i;

                 res *= i;

             }

         }

     }

     if (n > ) res *= (n - );

     return res;

 }

 //快速幂乘计算2^b % n

 int myPow(int b, int n)

 {

     if(b == ) return ;

     long long c = myPow(b >> , n);

     c = (c * c) % n;

     if(b & ) c = ( * c) % n;

     return c;

 }

 int main()

 {

     int n, x;

     bool ok;

     while(scanf("%d", &n) != EOF){

         ok = ;

         if((n & ) && (n - )){

             ok = ;

             int phi = Eular(n);

             for(x = ; x < phi; x++){

                 if(myPow(x, n) == ) break;

             }

         }

         if(ok) printf("2^%d mod %d = 1\n", x, n);

         else printf("2^%? mod %d = 1\n", n);

     }

     return ;

 }

巴特西

2^x mod n = 1（欧拉定理，欧拉函数，快速幂乘）

2^x mod n = 1

最新文章

热门文章