UVA10006 - Carmichael Numbers（筛选构造素数表+快速幂）

本文主要是介绍UVA10006 - Carmichael Numbers（筛选构造素数表+快速幂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA10006 - Carmichael Numbers（筛选构造素数表+快速幂）

题目链接

题目大意：如果有一个合数，然后它满足任意大于1小于n的整数a， 满足a^n%n = a;这样的合数叫做Carmichael Numbers。题目给你n，然你判断是不是Carmichael Numbers。

解题思路：首先用筛选法构造素数表，判断n是否是合数，然后在用快速幂求a^2-a^(n - 1）是否满足上述的式子。快速幂的时候最好用long long ,防止相乘溢出。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>const int maxn = 65000 + 5;
typedef long long ll;int notprime[maxn];void init () {for (int i = 2; i < maxn; i++) for (int j = 2 * i; j < maxn; j += i) notprime[j] = 1;
}ll powmod(ll x, ll n, ll mod) {if (n == 1)return x;ll ans = powmod(x, n / 2, mod);ans = (ans * ans) % mod;if (n % 2 == 1)ans *= x;return ans % mod;    
}bool is_carmichael(int n) {for (int i = 2; i < n; i++) {if (powmod(i, n, n) != i)return false;}return true;
}int main () {init();int n;while (scanf ("%d", &n) && n) {if (notprime[n] == 0)printf ("%d is normal.\n", n);else {bool flag = is_carmichael(n);if (flag)printf ("The number %d is a Carmichael number.\n", n);elseprintf ("%d is normal.\n", n);}}return 0;
}

这篇关于UVA10006 - Carmichael Numbers（筛选构造素数表+快速幂）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---