题目描述
https://codeforces.com/gym/103466/problem/E
简要题意：令 $f_d$ 表示三维空间中与原点 $(0,0,0)$ 距离为 $d$ 的整点个数，给定 $l,r,k,p$，求 $\sum_{i=l}^r(f_i~xor~k)\bmod p$
$l\le r\le 10^{13},r-l+1\le 10^6,k\le 10^{18},p\le 3+10^{13}$
Solution
对 $\frac{f_d}{6}$ 打表能够发现这是一个积性函数，同时可以得到当 $p\bmod 4\equiv 1$ 时，$f_{p^k}=p^k$，当 $p\bmod 4 \equiv 3$ 时，$f_{p^k}=p^k+2\frac{p^k-1}{p-1}$，知道这个之后我们直接区间筛即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
#define maxn 4000010
#define ll long long
using namespace std;
ll l, r, k, p;
int pri[maxn], cnt; bool isp[maxn];
void init_isp(int n) {
for (int i = 2; i <= n; ++i) {
if (!isp[i]) pri[++cnt] = i;
for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
isp[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}
ll v[maxn], ans[maxn];
ll solve(ll l, ll r, ll k, ll p) {
for (ll i = l; i <= r; ++i) v[i - l] = i, ans[i - l] = 1;
for (int i = 1, pr = pri[i]; i <= cnt && pr <= r / pr; pr = pri[++i])
for (ll j = max(2ll, (l + pr - 1) / pr) * pr; j <= r; j += pr) {
ll mk = 1;
while (v[j - l] % pr == 0) v[j - l] /= pr, mk *= pr;
if (pr == 2) mk = 1;
else if (pr % 4 == 3) mk += 2 * (mk - 1) / (pr - 1);
ans[j - l] *= mk;
}
for (ll i = l; i <= r; ++i) {
if (v[i - l] < 1) continue;
if (v[i - l] % 4 == 3) ans[i - l] *= v[i - l] + 2;
else ans[i - l] *= v[i - l];
} ll res = 0;
for (ll i = l; i <= r; ++i) res = (res + (ans[i - l] * 6 ^ k)) % p;
return res;
}
void work() {
cin >> l >> r >> k >> p;
cout << solve(l, r, k, p) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T; init_isp(4000000);
while (T--) work();
return 0;
}
|