首页 > 代码库 > 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);
else
printf ("%d is normal.\n", n);
}
}
return 0;
}
UVA10006 - Carmichael Numbers(筛选构造素数表+快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。