首页 > 编程语言 >挑战程序设计竞赛 2.6章习题 UVA - 10006 Carmichael Numbers

挑战程序设计竞赛 2.6章习题 UVA - 10006 Carmichael Numbers

时间:2024-04-04 12:33:38浏览次数:23  
标签:10006 int number 一个 素数 Numbers 测试 习题 Carmichael

https://vjudge.csgrandeur.cn/problem/UVA-10006

 当今计算机科学的一个重要的领域就是密码学。有些人甚至认为密码学是计算机科学中唯一重要的领域,没有密码学生命都没有意义。
  阿尔瓦罗就是这样的一个人,它正在设计一个为西班牙杂烩菜饭加密的步骤。他在加密算法中应用了一些非常大的素数。
  然而确认一个非常大的数是不是素数并不是那么简单。一个费时的方法是用比这个数的平方根小的所有素数去除它,
  对于大整数来说,这样一定会毁掉这个杂烩菜饭的。
  然而,一些很有信心耗时少的随机测试存在,其中一个就是费马测试。
  在2和n-1之间随机选取一个数(n是我们要测试的数)。如果a n mod n = a 成立,n就可能是一个素数。
  如果一个数通过费马测试很多次那么它就很可能是一个素数。
  不幸的是,一些数不是素数但是它们依然能通过每一个比它小的数的费马测试。这些数被称作卡迈克尔数
  这道题要求你写一个程序去测试给定的数是不是一个卡迈克尔数。
  完成了这个任务的队伍有希望接受来自阿尔瓦罗的西班牙杂烩菜饭23333

Input
多组输入,第一行给一个n (2 < n < 65000) 。n = 0 表示输入结束并不需要处理
Output
对每组输入,输出它是不是卡迈克尔数,参考样例。

Sample Input
1729
17
561
1109
431
0

Sample Output
The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.

解答
题意是找出一些和素数性质类似,但是不是素数的卡米尔数。
对于一个数n, 如果2和n-1之间的数a(n是我们要测试的数)。a^n mod n = a 均成立,n就可能是一个素数。
如果n不是素数,他就是卡米尔数

那么我们先打表 记录数据范围内所有的素数,然后保证n在表里面,逐个检测2和n-1 是否符合a^n mod n = a .
就可以判断是不是卡米尔数了。 a^n使用快速幂计算。
代码如下

#include <iostream>
#include <unordered_set>

using namespace std;


int n;
unordered_set<int> ss;
const int N = 65010;
int primes[N], cnt;
bool st[N];

void get_primes(int t) {
	for (int i = 2; i <= t; i++) {
		if (!st[i]) {
			primes[cnt++] = i;
			ss.insert(i);
		}
		for (int j = 0; primes[j] <= t / i; j++) {
			st[primes[j] * i] = true;
			if (i % primes[j] == 0) break;
		}
	}
}

int quickmi(long long a, long long b, long long m) {
	long long ans = 1;
	while (b) {
		if (b & 1) {
			ans = ans * a % m;
		}
		b >>= 1;
		a = a * a % m;
	}

	return ans;
}

void solve() {
	if (ss.count(n) != 0) {
		cout << n << " is normal." << endl;
		return;
	}

	for (int i = 2; i < n; i++) {
		if (quickmi(i, n, n) != i) {
			cout << n << " is normal." << endl;
			return;
		}
	}

	cout << "The number "<< n<< " is a Carmichael number." << endl;
	return;
}

int main()
{
	get_primes(N);
	while (cin >> n) {
		if (0 == n) break;
		solve();
	}

	return 0;
}

标签:10006,int,number,一个,素数,Numbers,测试,习题,Carmichael
From: https://www.cnblogs.com/itdef/p/18114080

相关文章

  • 攻防世界Misc新手习题集
    攻防世界Misc新手习题集日期:2024.04.01from故人叹、1.Ditf考察点:png图片改宽高、流量分析附件给到一张图片,拖入010分析,发现底部有CRC报错信息,怀疑原始宽高被更改。尝试更改高度,获得一段编码,可能为某个压缩包的密码。StRe1izia将图片进行foremost分离,发现一个加密压......
  • 大学教材《C语言程序设计》(浙大版)课后习题解析 | 第九、十章
    概述    本文主要提供《C语言程序设计》(浙大版)第九、十章的课后习题解析,以方便同学们完成题目后作为参考对照。后续将更新第十一、十二章节的课后习题解析,如想了解更多,请持续关注该专栏。专栏直达链接:《C语言程序设计》(浙大版)_孟俊宇-MJY的博客-CSDN博客​http://......
  • P1957 口算练习题
    题目描述王老师正在教简单算术运算。细心的王老师收集了 i 道学生经常做错的口算题,并且想整理编写成一份练习。编排这些题目是一件繁琐的事情,为此他想用计算机程序来提高工作效率。王老师希望尽量减少输入的工作量,比如 5+85+8 的算式最好只要输入 55 和 88,输出的结果......
  • 攻防世界Misc新手习题集
    攻防世界Misc新手习题集日期:2024.04.01from故人叹、1.Ditf考察点:png图片改宽高、流量分析附件给到一张图片,拖入010分析,发现底部有CRC报错信息,怀疑原始宽高被更改。尝试更改高度,获得一段编码,可能为某个压缩包的密码。StRe1izia将图片进行foremost分离,发现一个加密压......
  • python基础(四)----列表、字典练习题
    好友管理系统请设计一个好友管理系统,每个功能都对应一个序号,用户可根据提示“请输入您的选项”选择序号执行相应的操作,包括:(1)添加好友:用户根据提示“请输入要添加的好友:”输入要添加好友的姓名,添加后会提示“好友添加成功”。(2)删除好友:用户根据提示“请输入删除好友姓名:”输入要删......
  • Python列表、字典、元组练习题
    一、将下列姓名长度小于2字符的删除,将写法不同但名字一样的名字合并,并按首字母大写形式输出。names=[‘Bob’,‘JOHN’,‘alice’,‘bob’,‘ALICE’,‘J’,‘Bob’]答案:names=['Bob','JOHN','alice','bob','ALICE','J','Bob']ans={name.title()for......
  • 猜数字-周末习题
    程序随机内置一个位于一定范围内的数字作为猜测的结果,由用户猜测此数字。用户每猜测一次,由系统提示猜测结果:太大了、太小了或者猜对了,直到用户猜对结果或者猜测次数用完导致失败。importrandomnum=random.randint(0,99)count=0whilecount<3:guess=int(input("please......
  • 00342第四章 结构化程序设计 思考题和练习题(C语言)
    一、单项选择题1.若从键盘输入字符串"HOWAREYOU?",可以直接使用库函数【】。        A.scanf    B.getstr    C.gets    D.都不能直接使用2.C语言的库函数中,可以输出double型变量值的是【】。        A.getchar   ......
  • 大学教材《C语言程序设计》(浙大版)课后习题解析 | 第七、八章
    概述    本文主要提供《C语言程序设计》(浙大版)第七、八章的课后习题解析,以方便同学们完成题目后作为参考对照。后续将更新第九、十章节的课后习题解析,如想了解更多,请持续关注该专栏。专栏直达链接:《C语言程序设计》(浙大版)_孟俊宇-MJY的博客-CSDN博客​http://t.cs......
  • 大学教材《C语言程序设计》(浙大版)课后习题解析 | 第五、六章
    概述   本文主要提供《C语言程序设计》(浙大版)第五、六章的课后习题解析,以方便同学们完成题目后作为参考对照。后续将更新第七、八章节课后习题解析,如想了解更多,请持续关注该专栏。专栏直达链接:《C语言程序设计》(浙大版)_孟俊宇-MJY的博客-CSDN博客http://t.csdnimg......