HDU1395 2^x mod n = 1 暴力题

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1395

可以用欧拉定理证明其存在性。

欧拉定理是这样的：

如果a和m互质且a<m,设x为欧拉函数的值，则a^x%m=1

因此在本题中，只要所给的数为奇数，即和2互质，则一定存在解，再暴力就可以了

#include<cstdio>
int main()
{
    int n;
    while (scanf("%d", &n) != EOF){
        if (n % 2 && n > 2){
            int m = 1;
            for (int i = 1;; i++){
                if ((m = m * 2 % n)==1){
                    printf("2^%d mod %d = 1
", i, n);
                    break;
                }
            }    
        }
        else
            printf("2^? mod %d = 1
", n);
    }
    return 0;
}