题目链接
思路：本来以为如果是偶数就？ 奇数就 5 = 2*2 + 1 所以就是 2的4次方 。WA！ 例如， 2^x mod 7 = 1. 这样的答案是
7 = 2 * 3 + 1 是6吗？ 6的确对，但是要保证最小。所以思路错误。看了题解。了解到费马小定理，还是欧拉定理能够得到奇数必有解。
AC代码：（暴力求解）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int main() {
int n;
while(~scanf("%d", &n)) {
if(n&1 && n != 1) {
int res = 1, t = 2;
while(t%n != 1) {
t = t*2%n;
res++;
}
printf("2^%d mod %d = 1n", res, n);
} else {
printf("2^? mod %d = 1n", n);
}
}
}
思路：
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代码：
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int eular(int n) {
int ans = n;
for(int i = 2; i*i <= n; i++) {
if(n % i == 0) {
ans -= ans / i;
while(n % i == 0) {
n /= i;
}
}
}
if(n > 1) ans -= ans / n;
return ans;
}
ll mod_pow(ll x, ll n, ll mod) {
ll res = 1;
while(n > 0) {
if(n&1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
int main() {
int n;
while(~scanf("%d", &n)) {
if(n&1 && n != 1) {
int zhi = eular(n);
for(int i = 1; i <= zhi; i++) {
if(mod_pow(2, i, n) == 1) {
printf("2^%d mod %d = 1n", i, n);
break;
}
}
} else {
printf("2^? mod %d = 1n", n);
}
}
}
