令 \(\text{nxt}_i\) 为 \(i\) 之后的第一个质数。
考虑最后 \(a_i\) 会变成什么。
首先第一种就是直接变为 \(\max a_i\)。
其次还发现可能变为 \(\operatorname{nxt}_{\max a_i}\)。
对于其他的，可以证明一定不优于这两种，因为其他的情况无非就是在这基础上继续跳 \(\operatorname{nxt}\) 或 \(+1\)，并没有更快的“捷径”能够跳到这些地方，要到达这个状态肯定要通过上述说过的两种状态。
于是就只需要解决目标是其中之一的最小值，最后取 \(\min\) 即可。
接下来就考虑怎么求最小值。
不难发现对于其中一个 \(a_i\) 的路径，可以拆为，先跳若干次 \(\operatorname{nxt}\)，最后再一直 \(+1\)（因为 \(\operatorname{nxt}\) 已经大于了目标）。
对于后面 \(+1\) 的明显只能用 \(c1\) 处理。
但对于前面跳 \(\operatorname{nxt}\)，可以记录下跳的距离 \(d\)，当 \(c_1 d\le c_2\) 即 \(d\le \frac{c_1}{c_2}\)，用 \(c_1\) 去替代更优。
上述提到的过程都可以用前缀和来优化。
时间复杂度 \(\mathcal{O}(V\log \log V + n + q)\)，\(V\) 为值域。
用欧拉筛即可以使 \(V\) 部分的复杂度变为线性。
#include<bits/stdc++.h>
using ll = long long;
#define gc getchar_unlocked
inline int read() {
int x = 0, c = gc();
while (! isdigit(c)) c = gc();
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
return x;
}
const int maxn = 1e5 + 10, limm = (int)1e7 + 19, limcnt = 664580, limd = 154;
const ll lim = (1 << 17) - 1;
std::bitset<limm + 2> vis;
int pr[limcnt + 2], cnt, nxt[limm + 2];
std::unordered_map<int, int> id;
int a[maxn];
int to[2];
ll c1[2], c2[2][limd + 2], s2[2][limd + 2]; int sum[limcnt + 2];
int main() {
for (int i = 2; i * i <= limm; i++)
if (! vis[i]) {
for (int j = i * i; j < limm; j += i)
vis[j] = 1;
}
for (int i = 2; i <= limm; i++)
! vis[i] && (pr[++cnt] = i, id[i] = cnt);
for (int i = limm, w = -1; i; i--)
nxt[i] = w, ! vis[i] && (w = i);
int n = read(), m = read(), T = read();
for (int i = 1; i <= n; i++) a[i] = read();
int mx = a[1];
for (int i = 2; i <= n; i++) mx = std::max(mx, a[i]);
to[0] = mx, to[1] = nxt[mx];
for (int op : {0, 1}) {
int ed = to[op], pre = 0;
for (int i = cnt; i; i--)
if (pr[i] <= ed) {pre = i; break;}
memset(sum, 0, sizeof(sum));
for (int i = 1, x; i <= n; i++) {
x = a[i];
if (nxt[x] <= ed) {
c2[op][nxt[x] - x]++, s2[op][nxt[x] - x] += nxt[x] - x;
x = nxt[x];
sum[id[x]]++;
x = pr[pre];
}
c1[op] += ed - x;
}
for (int i = 1; i < pre; i++) {
sum[i] += sum[i - 1];
c2[op][pr[i + 1] - pr[i]] += sum[i], s2[op][pr[i + 1] - pr[i]] += 1ll * sum[i] * (pr[i + 1] - pr[i]);
}
for (int i = 1; i <= limd; i++)
c2[op][i] += c2[op][i - 1], s2[op][i] += s2[op][i - 1];
}
for (ll w1, w2, ans = 0; m--; ) {
w1 = read() ^ (T ? (ans & lim) : 0), w2 = read() ^ (T ? (ans & lim) : 0);
ans = 1e18;
for (int op : {0, 1})
ans = std::min(ans, w1 * (c1[op] + s2[op][std::min((int)(w2 / w1), limd)]) + w2 * (c2[op][limd] - c2[op][std::min((int)(w2 / w1), limd)]));
printf("%lld\n", ans);
}
return 0;
}