UVA 10006（快速幂+暴力）

2019-04-14 08:19发布

站内文章 / 模拟电子
14325 0 1684

题意

给你一个数n，问你这个数是不是卡迈克尔数。如果一个数是合数且满足对于每一个比它小的数a都有an=a(模n下)" role="presentation" style="position: relative;">an=a(模n下);

分析

暴力判断即可，但是要注意先判断是否是质数，如果是质数一定不是卡迈克尔数，就不需要进行费马检验了。否则亲测超时。

代码

#include #include using namespace std; typedef long long int ll; bool flag1 = false, flag2 = false; int m; inline ll pow_m(ll a, ll b, ll mod) { ll res = 1; while (b) { if (b & 1) res = (res*a) % mod; a = (a*a) % mod; b >>= 1; } res = res % mod; return res; } int main() { int n; ios::sync_with_stdio(false); while (cin >> n && n) { flag1 = false, flag2 = false; m = sqrt(n + 0.5); for (int i = 2; i <= m; i++) { if (n%i == 0) { flag2 = true; break; } } if (!flag2) { cout << n << " is normal." << endl; continue; } for (int i = 2; i <= n - 1; i++) { int aa = pow_m(i, n, n); if (aa != i) { flag1 = true; break; } } if (!flag1&&flag2) cout << "The number " << n << " is a Carmichael number." << endl; else cout << n << " is normal." << endl; } }

热门文章