2022-03-26每日刷题打卡
2022-03-26每日刷题打卡
代码源——每日一题
RSA - 题目 - Daimayuan Online Judge
RSA算法选择两个不同质数的积作为模数。现在有两个正整数 A,B，如果它们是不同的质数，则判定为 full credit；否则，如果A⋅B不是任意大于1的整数的平方的整数倍，则判定 partial credit；否则判定为no credit。
输入格式
一行两个正整数 A,B。
输出格式
full credit 或 partial credit 或 no credit。
样例1输入
13 23
样例1输出
full credit
先判断a和b是否相等，如果相等直接输出no credit，因为他们的乘积一定是平方数的倍数
求出a和b的所有因子，并记录下所有因子的出现次数，
- 如果有一个因子出现了两次以上，或者已经有一个因子是某个数的平方数时，输出no credit
- 如果这两个数没有除了1和自身以外的数，就输出full credit
- 剩余情况输出partial credit
试除法求数num的全部因子，复杂度为:O(sqrt(num))。
（虽然这题直接对a和b分解质因数，计算质因数的出现次数即可，但是试除法更便于新手理解。）
#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！