首页 > 代码库 > UVA 1404 - Prime k-tuple(素树筛选)
UVA 1404 - Prime k-tuple(素树筛选)
UVA 1404 - Prime k-tuple
题目链接
题意:找出a-b之间有多少个素数k元组,并且最后一个元素减第一个元素为s
思路:先筛出sqrt的素数,然后对于每个区间,在用这些素数去筛出区间的素数,然后twopointer搞一下即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> #include <vector> using namespace std; typedef long long ll; int t, a, b, k, s; vector<int> save; int pow_mod(int x, int k, int mod) { int ans = 1; while (k) { if (k&1) ans = (ll)ans * x % mod; x = (ll)x * x % mod; k >>= 1; } return ans; } bool mlrb(int x) { if (x == 1 || x == 0) return false; for (int i = 0; i < 15; i++) { int a = rand() % (x - 1) + 1; if (pow_mod(a, x - 1, x) != 1) return false; } return true; } const int N = 10000005; const int M = 100005; int prime[M], pn = 0, vis[N]; void getprime() { for (int i = 2; i < M; i++) { if (vis[i]) continue; prime[pn++] = i; for (ll j = (ll)i * i; j < M; j += i) vis[j] = 1; } } int main() { getprime(); int now = 0; for (int i = 0; i < M; i++) { if (prime[now] == i) { now++; continue; } vis[i] = 0; } scanf("%d", &t); while (t--) { scanf("%d%d%d%d", &a, &b, &k, &s); save.clear(); for (int i = 0; i < pn; i++) { if (prime[i] > b) break; int tmp = a / prime[i] * prime[i]; if (tmp < a) tmp += prime[i]; if (prime[i] == tmp) tmp += prime[i]; for (int j = tmp; j <= b; j += prime[i]) { vis[j - a] = 1; } } for (int i = a; i <= b; i++) { if (vis[i - a]) continue; save.push_back(i); } /*for (int i = a; i <= b; i++) { if (mlrb(i)) save.push_back(i); }*/ int n = save.size(); if (n == 0) { printf("0\n"); continue; } int pre = 0; int cnt = 0; int ans = 0; for (int i = 0; i < n; i++) { cnt++; if (cnt >= k || save[i] - save[pre] >= s) { if (cnt == k && save[i] - save[pre] == s) ans++; while (cnt >= k || save[i] - save[pre] >= s) { pre++; cnt--; } } } printf("%d\n", ans); int now = 0; for (int i = a; i <= b; i++) { if (i == save[now]) { now++; continue; } vis[i - a] = 0; } } return 0; }
UVA 1404 - Prime k-tuple(素树筛选)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。