/*
* [题意]
* 输入n,若满足如下两个条件,则n是Carmichael number
* 1、n不是素数
* 2、对于所有a(2<=a<n),有(a^n)%n = a
*
* [解题方法]
* 快速幂取模,注意运算过程中的乘法溢出int
*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define LL long long
#define M 65000
#define inf 0x3fffffff
int vis[M];
int qmod (int a, int b, int c) //二进制思想快速求(a^b)%c
{
int res = 1;
for ( ; b; b >>= 1)
{
//强制转换LL,是因为乘法有可能溢出
if (b & 1) res = (LL)res*a % c;
a = (LL)a*a % c;
}
return res;
}
int main()
{
int n, a, i, j;
for (i = 2; i < M; i++) //素数筛法
if (!vis[i])
for (j = i+i; j < M; j+=i)
vis[j] = 1;
while (scanf("%d", &n), n)
{
if (!vis[n]) //是素数
{
printf ("%d is normal.\n", n);
continue;
}
for (a = 2; a < n; a++)
if (qmod(a, n, n) != a)
break;
if (a < n) printf ("%d is normal.\n", n);
else printf ("The number %d is a Carmichael number.\n", n);
}
return 0;
}
分享到:
相关推荐
如果奇合数m满足;对每一个整数α,(α,m)=1,均有am-1(modm),则m 称为Carmichael数.本文给出一种探求大Carmichael数的方法,并给出一些超过108300的 Carmichael数。
设Ck(k>0)表示k阶Carmichael数集,C1即为通常的Carmichael数集.作者考虑3阶Carmichael数的性质,得到了n∈C3的一个必要条件(定理1)和两个容易计算的充分条件(定理2和定理3)。对于10 8以下,发现了43个3阶...
matlab植入代码欢迎来到我的Carmichael号码仓库! 此回购旨在复制和扩展我的硕士论文中所做的研究: 这项研究最初是在2009年至2011年之间完成的,并且在很大程度上取决于cpu的计算能力。 我创建此存储库的原因之一是...
k阶广义Carmichael数集Ck,在k = 2,3时有比较简单的判定条件.作者给出了k≥ 4时类似的充分条件,并给出k=4时充分条件不必要的具体例子.
设p,q是不同的奇素数。证明了:如果,n=pq,则n不是适合n3-1≡0(modp2-1)和n3-1≡0(modq3-1)的三个阶Carmichael数。
鞍点近似From:Joshua Carmichael
通过将用户友好的飞机建模与快速...• NACA456 – Ralph Carmichael (PDAS) – 计算 NACA 6 系列翼型纵坐标 除了每次调整飞机模型时都会更新的内置线性化稳定性近似值外,该程序还与以下软件接口以进行更高级的分析
众神网站carmichael payamps
所以91是基3的伪素数由于课上没有介绍, 我们这里首先证明一下Korselt定理:定理 1. 一个合数是Carmichael数, 当且仅当对其每一个素因子p都有
Gmaz、Carmichael 和 van der Meer 的代码和预处理数据文件,“大鼠伏隔核中结果预测提示特征的持续编码”(2018 年)()。 该代码使用 ,并使用 MATLAB R2015a 在 Windows 7 上进行了测试。 请参阅许可信息。 要...
bootstrapx clickover提供了对增强,以允许通过单击事件...版权所有2012 Lee Carmichael 根据Apache许可证2.0版(“许可证”)获得许可; 除非遵守许可,否则您不得使用本作品。 您可以在LICENSE文件中或以下位置获得
数学计算的计算机方法 通过Nikolai Shokhirev 1.简介 George Forsythe,Michael ... 但是,拉尔夫·卡迈克尔(Ralph Carmichael)将其翻译为现代版本的FOFTRAN:[3]。 他还添加了一些测试例程。 3. Pascal翻译 我将
[1] Freeman,William T和Pasztor,Egon C和Carmichael,Owen T,《学习低级视觉》,IJCV,2000年。 ( 等人首先提出了基于示例或基于学习的超分辨率框架-了解低分辨率图像块与高分辨率图像块之间的关系。) [2] ...
Carmichael, GR,2002 年。动力学预处理器 KPP——用于解决化学动力学问题的软件环境。 计算机与化学工程,26(11),第 1567-1579 页。 鉴于 KPP 已有十几年的历史,并非 KPP 的所有功能都受支持,并且生成的
语言:English,español 将键盘导航添加到各种网络漫画中。 此扩展允许使用箭头键对漫画进行键盘导航。...年龄Ménage的傻瓜à3 Buttersafe达尔文·卡迈克尔(Darwin Carmichael)将陷入地狱两种德累斯顿·科达
Bronfenbrenner, U. 童年的两个世界:美国和苏联 纽约:Russell Sage Foundation,1970,190 页,[美元]7.50 196 书注和评论 书评 环境、遗传和智力。...剑桥:哈佛教育评论,1969 ...Mussen,(Ed.)Carmichael 的儿
环境、遗传和智力。 剑桥:哈佛教育评论,1969 年,245 页,[美元]4.95 196 书注和评论书简述环境、遗传和智力。...Mussen,(Ed.)Carmichael 的儿童心理学手册,(第 1 卷)'1970 年,第 39-76 页)。 一般来说,
Table of Contents Summary of gdb . . . . . . . . ....Free Software ....Free Software Needs Free Documentation ....Contributors to gdb....1 A Sample gdb Session ....2 Getting In and Out of gdb ....2.1 Invoking gdb ....