Hackerrank--Prime Sum
The problem is quite simple. You're given a number N and a positive integer K. Tell if N can be represented as a sum of K prime numbers (not necessarily distinct).
Input Format
The first line contains a single integer T, denoting the number of test cases.
Each of the next T lines contains two positive integers, N & K, separated by a single space.Output Format
For every test case, output "Yes" or "No" (without quotes).Constraints
1 <= T <= 5000
1 <= N <= 1012
1 <= K <= 1012Sample Input
2
10 2
1 6
Sample Output
Yes
No
Explanation
In the first case, 10 can be written as 5 + 5, and 5 is a prime number. In the second case, 1 cannot be represented as a sum of prime numbers, because there are no prime numbers less than 1.
题意:给两个正整数n和k,问能否将n分解为k个素数的和(可以出现相同的)。
思路:本题涉及的知识点有哥德巴赫猜想(任何大于2的偶数都可以拆分成两个素数的和),
还有Miller-Rabin素数测试,一般使用的素数测试是O(sqrt(n))复杂度的,无法满足大整数的要求。
费马小定理: 如果p是一个素数,且(0<a<p),则
例如,67是一个素数,则2^66 mod 67=1.
利用费马小定理,对于给定的整数n,可以设计一个素数判定算法.通过计算d=2^(n-1) mod n 来判定整数n的素性.当d≠1时,n肯定不是素数;当d=1时,n则很可能是素数,但也存在合数n,使得 .例如,满足此条件的最小合数是n=341.为了提高测试的准确性,我们可以随机地选取整数1<a<n-1,然后用条件 来判定整数n的素性.例如对于n=341,取a=3时,有 ,故可判定n不是素数.
费马小定理毕竟只是素数判定的一个必要条件.满足费马小定理条件的整数n未必全是素数.有些合数也满足费马小定理的条件.这些合数被称作Carmichael数,前3个Carmichael数是561,1105,1729. Carmichael数是非常少的.在1~100000000范围内的整数中,只有255个Carmichael数.
利用下面的二次探测定理可以对上面的素数判定算法作进一步改进,以避免将Carmichael数当作素数.
二次探测定理 如果p是一个素数,且0<x<p,则方程x*x≡1(mod p)的解为x=1,p-1.
事实上, x*x≡1(mod p)等价于 x*x-1≡0(mod p).由此可知;
(x-1)(x+1) ≡1(mod p)
故p必须整除x-1或x+1.由p是素数且 0<x<p,推出x=1或x=p-1.
利用二次探测定理,我们可以在利用费马小定理计算 a^(n-1) mod n的过程中增加对于整数n的二次探测.一旦发现违背二次探测条件,即可得出n不是素数的结论.
Accepted Code:
#include <ctime>
#include <iostream>
using namespace std; typedef long long LL; LL mulMod(LL a, LL b, LL c) {
LL res = ;
while (b) {
if (b&) if ((res = (res + a)) >= c) res -= c;
a = a + a;
if (a >= c) a -= c;
b >>= ;
}
return res;
} LL powMod(LL a, LL b, LL c) {
LL res = ;
while (b) {
if (b&) res = mulMod(res, a, c);
a = mulMod(a, a, c);
b >>= ;
}
return res;
} bool isPrime(LL n) {
if (n <= ) return false;
if (n == ) return true;
if (n & == ) return false;
srand((LL)time());
LL u = n - , k = , pre;
while (!(u&)) u >>= , k++;
for (int t = ; t < ; t++) {
LL a = rand() % (n - ) + ;
LL ans = powMod(a, n - , n);
for (int i = ; i < k; i++) {
pre = ans;
ans = mulMod(ans, ans, n);
if (ans == && (pre != && pre != n - )) return false;
pre = ans;
}
if (ans != ) return false;
}
return true;
} int main(void) {
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
LL n, k;
cin >> n >> k;
if (n < * k) {
cout << "No" << endl;
} else {
if (k == ) {
if (isPrime(n)) cout << "Yes" << endl;
else cout << "No" << endl;
} else if (k == ) {
if (n % == ) cout << "Yes" << endl;
else if (isPrime(n - )) cout << "Yes" << endl;
else cout << "No" << endl;
} else {
cout << "Yes" << endl;
}
}
}
return ;
}
最新文章
- js 判断 是否位数字
- tabhost使用
- 转载和积累系列 - 深入理解HTTP协议
- Linux Apache和Nginx网络模型详解
- python中的namespace
- 机器人学 —— 轨迹规划(Configuration Space)
- Lotus 迁移到Exchange POC 之 新建2007 服务器!
- JAVA加密
- frame.origin.x 的意思和作用?
- Echarts展示百分比的问题
- 说出JQuery中常见的几种函数以及他们的含义是什么?
- ASP.NET CORE Linux发布工具(文件对比 只上传差异文件;自动启停WebServer命令;上传完成自动预热WebServer)
- 今天俺要说一说工厂方法模式(Factory)
- ImageMagick:获取一行文字的宽与高
- Codeforces.1028F.Make Symmetrical(结论 暴力)
- Linux中实现文本过滤
- vim常用
- 谈谈MySQL死锁之二 死锁检测和处理源码分析
- props传递数据
- 18-hadoop-weather案例