题目链接:uva 1404 1404 - Prime k-tuple
题目大意:如果k个相邻的素数p1,p2,…,pk,满足pk−p1=s,称这些素数组成一个距离为s的素数k元组,给定区间a,b,求有多少个距离s的k元组。
解题思路:筛选素数法,先预处理出[1, sqrt(inf)]的素数表,然后对给定区间[a,b]根据预处理出的素数表筛选出素数即可。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int sqrt_inf = 46340;
const int maxn = 2 * 1e9;
int np, pri[sqrt_inf];
bool vis[maxn+5];
vector<int> vec;
void prime_table (int n) {
np = 0;
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= n; i++) {
if (vis[i])
continue;
pri[np++] = i;
for (int j = i * i; j <= n; j += i)
vis[j] = 1;
}
}
int solve () {
int ret = 0;
int a, b, s, k;
vec.clear();
memset(vis, 0, sizeof(vis));
scanf("%d%d%d%d", &a, &b, &k, &s);
for (int i = 0; i < np && pri[i] * pri[i] <= b; i++) {
int u = pri[i], d = (u - a % u) % u;
if (u == a + d)
d += u;
while (d <= b - a) {
vis[d] = 1;
d += u;
}
}
for (int i = 0; i <= b-a; i++) {
if (vis[i] == 0 && a + i > 1)
vec.push_back(a+i);
}
for (int i = 0; i + k - 1 < vec.size(); i++) {
if (vec[i+k-1] - vec[i] == s)
ret++;
}
return ret;
}
int main () {
prime_table(sqrt_inf);
int cas;
scanf("%d", &cas);
while (cas--) {
printf("%d\n", solve());
}
return 0;
}
分享到:
相关推荐
——学习参考资料:仅用于个人学习使用! 本代码仅作学习交流,切勿用于商业用途,否则后果自负。若涉及侵权,请联系,会尽快处理! 未进行详尽测试,请自行调试!
06.hive中的json解析函数--json-tuple.mp4
藏经阁-std__tuple与模板元编程.pdf
测量程序编制 - python 27数据类型:Tuple(元组)-概述.pptx
这些实现最终将被合并到适当的Clojure,但是现在可以通过更换使用vector与clj-tuple/vector和hash-map与clj-tuple/hash-map 。 用法 [clj-tuple " 0.2.2 " ] clj-tuple> ( vector 1 2 3 ) [ 1 2 3 ] clj-tuple> ( ...
Tuple(元组) - 装包与拆包 装包与拆包 Python中,元组装包拆包是自动的,不需要任何函数,导致很多人对于函数返回值一会有括号一会没括号非常迷惑 a,b,c=1,2,3 #等价于 a,b,c=(1,2,3) print(a,type(a)) #因为等号...
Tuple(元组)-创建;Python创建元组;Python创建元组;
移动到https://github.com/mike-k-houghton/tuplespace元组是项目的有序列表。 元组空间是一种关联存储器,其中条目,元组存储在该空间中,并使用基于元组的内在属性的搜索条件进行检索。 这两个关键操作被放置在...
整型--int 布尔型--bool 字符串--str 列表--list 元组--tuple 字典--dict
Tuple(元组) namedtuple(具名元组)具名元组具名元组:因为元组的局限性:不能为元组内部的数据进行命名,所以往往我们并不知道一个元组所要表达的意义,所以在这里引入了?collections.namedtuple?这个工厂函数,来...
输入一个三元组表,先输出其矩阵形态,然后对其进行转置并输出转置后的矩阵
Tuple ,深度不变的类似数组的结构#[1, 2, 3, 4] 记录和元组只能包含基元以及其他记录和元组。 您可以将Records和Tuples视为“复合原语”。 通过完全基于基元而不是对象,Records和Tuples完全不可变。 记录和元组...
Print out the per-protocol part of the tuple.
Print out the per-protocol part of the tuple.
Print out the per-protocol part of the tuple.
Objective-C Tuple,OC实现的元组
py代码-list和tuple
“#Basic-Python-Interpreter”
tuple_utility, 缺少的C++ tuple 功能 tuple_utilityC++ 元组的实用工具。tuple_map:#include"tuple_utility.hpp"int main(){ auto t = std::make_tuple(0, 1