题目描述
YJC把核弹发射密码忘掉了……其实是密码被加密了，但是YJC不会解密。密码由n个数字组成，第i个数字被加密成了如下形式：第k小的满足(2^L)|(P-1)且P为质数的P。YJC希望你能帮他算出密码是多少。
输入输出格式
输入格式：
第一行包含一个整数n，表示密码中的数字个数。
接下来n行每行两个整数L和k，表示一个数字的加密形式。
注意，输入格式变更，请注意L和k的先后顺序
输出格式：
输出n行，第i行一个整数，表示第i个数字。
输入输出样例
输入样例#1：
2 21 92 23 9
输出样例#1：
1998585857 998244353
说明
对于50%的数据，满足18≤n,L≤1000。
对于100%的数据，满足12≤n,L≤500000，保证答案<2^31。
分析：比较考验人品的一道题。
暴力找的话有30分.时间都浪费在了怎么判断素数上，而且询问很多，每个数可能会被判断多次，考虑怎么优化它们.
对于素数的判断，可以用一个比较考验人品的算法miller rabin测试，每一次都有大约1/4的概率会出错，因此要多判几次，但是多判几次又会超时，将次数控制在3次到5次就可以了.这里利用费马小定理+快速幂进行判断.
接下来考虑怎么不重复判断同一个数。我们将询问的L按照降序排序,符合条件的数肯定是k*2^i+1的形式，我们先从大到小枚举i,再枚举k,k枚举的是奇数，因为如果我们一个一个地枚举，如果k=2,那么就会跳到2^(i+1) + 1上去，而我们之前已经计算过了这个数，会造成重复.将所得的素数排个序.
最后考虑怎么快速得到第k小的p,因为我们已经将所得的素数排好序了，所以我们可以二分查找，由于之前我们将询问的L按照降序排列，那么得到的满足要求的数就构成了一个又一个的区间，那么利用树状数组来维护有多少个比它小的就可以了.
听说还有还可以用等差数列筛法，orz
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1 << 20,maxm = 600010; long long n,cnt,num[maxm],prime[maxm],t[maxm],ans[maxm],c[maxm]; struct node { long long l, k; int id; }e[maxm]; long long qpow(long long a, long long b, long long mod) { long long ans = 1; while (b) { if (b & 1) ans = (ans * a) % mod; b >>= 1; a = (a * a) % mod; } return ans; } bool isok(long long x) { if (qpow(7, x - 1, x) == 1 && qpow(13, x - 1, x) == 1 && qpow(19, x - 1, x) == 1) return true; return false; } bool cmp1(node a, node b) { return a.l > b.l; } int main() { scanf("%lld", &n); for (int i = 1; i <= n; i++) { scanf("%lld%lld", &e[i].l, &e[i].k); e[i].id = i; } sort(e + 1, e + 1 + n, cmp1); for (int i = 30; i >= 12; num[i--] = cnt) for (int j = 1; 1LL * j * (1 << i) < (1LL << 31) - 1; j += 2) if (isok(j * (1 << i) + 1)) prime[++cnt] = j * (1 << i) + 1; memcpy(t, prime, sizeof(prime)); sort(t + 1, t + 1 + cnt); for (int i = 1; i <= cnt; i++) prime[i] = lower_bound(t + 1, t + 1 + cnt, prime[i]) - t; //实际上是把符合要求的质数和离散化了 int cur = 1; for (int i = 1; i <= n; i++) { while (cur <= num[e[i].l]) { for (int j = prime[cur]; j < maxn; j += j & -j) c[j]++; cur++; } int l = 0, r = maxn, sum = 0;; while (l<r) { int mid = (l + r) >> 1; sum += c[mid]; if (sum >= e[i].k) { sum -= c[mid]; r = mid; } else l = mid + 1; } ans[e[i].id] = t[l]; } for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
return 0; }