hdoj1395（暴力求解）

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

思路：
1.因为很容易就出现超出范围的情况，所以我们需要对每次运算结果对n取模；
2.然后从2开始，每次计算都是2次幂，采用暴力枚举。

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        if(n%2 == 0 || n == 1)
        {
            cout << "2^? mod " << n << " = 1" << endl;
        }
        else
        {
            int i = 1;
            long long s = 2;
            while(s % n != 1 && i < 500)
            {
                s <<= 1;
                s %= n;
                i ++;
            }
            if(s % n == 1)
            {
                cout << "2^" << i << " mod " << n << " = 1" << endl;
            }
            else
            {
                cout << "2^? mod " << n << " = 1" << endl;
            }
        }
    }
    return 0;
}