2 ^ x mod n = 1问题

问题介绍:给一个整数n，找到最小的x(x > 0),使满足 2 ^ x mod n = 1

问题解析:对于a * b % c 有公式:    a * b % c = ((a % c) * (b % c)) % c.

　　　　所以可以通过递归求解a ^ b mod c.穷举x，便可写出以下代码:

　　　　

#include<stdio.h>
#include<iostream>
using namespace std;

//a ^ b % c
int get_mod(__int64 a, int b, int c)
{
    if(b == 1)
        return a % c;
    return get_mod(a, b - 1, c) * a % c;
    //((a ^ (b - 1) % c) * a) % c
}


int main()
{
    int n;
    while(cin>>n)
    {
        if(n % 2 == 0 || n <= 1)
            printf("2^? mod %d = 1
", n);
        else
        {
            int x;
            for(x = 1; ; x++)
                if(get_mod(2, x, n) == 1)
                {
                    printf("2^%d mod %d = 1
", x, n);
                    break;
                }
        }
    }
    return 0;
}
 

显然，当n比较大时，上述算法的效率很低，最终导致超时...需要修改莫幂运算的算法.

　　　需要使用一种数学方法:蒙哥马利幂模运算(是快速计算a^b%k的一种算法).

　　   由于a * a % c =  ((a % c) * (a % c)) % c   =  ((a % c)^2) % c. 可以将两次运算转换为一次乘方运算.

　　   所以可以通过这样的递归公式:a ^ 2n % c = (a ^ n % c) ^ 2 % c.可以二分计算.

　　  效率由原来的n变为log2(n).当n很大时，效率提升数万倍.

　　  注意,当n为奇数时，需要利用正常的递推方法使n - 1为偶数带入下一次计算.

　　　修改后的代码:

　　　

//给一个整数n，找到最小的x(x > 0),使满足 2 ^ x mod n = 1

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;

//a ^ b % c
int get_mod(__int64 a, int b, int c)
{
    if(b == 1)
        return a % c;
    if(b % 2 == 1)
        return (get_mod(a, b - 1, c) * (a % c)) % c;
    return (int)pow(get_mod(a, b / 2, c), 2) % c; 
    //((a ^ (b - 1) % c) * a) % c
}


int main()
{
    int n;
    while(cin>>n)
    {
        if(n % 2 == 0 || n <= 1)
            printf("2^? mod %d = 1
", n);
        else
        {
            int x;
            for(x = 1; ; x++)
                if(get_mod(2, x, n) == 1)
                {
                    printf("2^%d mod %d = 1
", x, n);
                    break;
                }
        }
    }
    return 0;
}