BZOJ2693 jzptab <莫比乌斯反演>

Problem

jzptab


Description

,答案模 输出。
多组询问。

Input

一个正整数 表示数据组数。
接下来 行,每行两个正整数 表示

Output

行,每行一个整数,表示第 组数据的结果。

Sample Input

1
2
1
4 5

Sample Output

1
122

HINT


Sourse

版权所有者:倪泽堃

标签:莫比乌斯反演

Solution

此题和 所求相同,只是又多组询问,如果每次都像 那样 做为 。故需要改变求和方式。这里将使用 的最终推导结果来继续恒等变形。前面的推导见:BZOJ2154



综上, 的前缀和可用线性筛预处理,对于每次询问对 根号分块,即可做到 的复杂度。

Code

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
#include <bits/stdc++.h>
#define MAX_N 10000000
#define MOD 100000009
using namespace std;
typedef long long lnt;
template <class T>
inline void read(T &x) {
x = 0; int c = getchar(), f = 1;
for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt n, m, cnt, ans, s[MAX_N+5], pri[MAX_N+5]; bool NotPri[MAX_N+5];
void init() {
NotPri[1] = true, s[1] = 1;
for (lnt i = 2; i <= MAX_N; i++) {
if (!NotPri[i]) pri[cnt++] = i, s[i] = (i-i*i%MOD)%MOD;
for (int j = 0; j < cnt; j++) {
if (i*pri[j] > MAX_N) break;
NotPri[i*pri[j]] = true;
if (i%pri[j]) s[i*pri[j]] = s[i]*s[pri[j]]%MOD;
else {s[i*pri[j]] = s[i]*pri[j]; break;}
}
}
for (int i = 1; i <= MAX_N; i++) (s[i] += s[i-1]) %= MOD;
}
int main() {
int T; read(T), init();
while (T--) {
lnt n, m; read(n), read(m), ans = 0;
for (lnt l = 1, r; l <= min(n, m); l = r+1)
r = min(n/(n/l), m/(m/l)), (ans += (n/l*(n/l+1)/2%MOD)*(m/l*(m/l+1)/2%MOD)%MOD*(s[r]-s[l-1])%MOD) %= MOD;
printf("%lld\n", (ans+MOD)%MOD);
}
return 0;
}
------------- Thanks For Reading -------------
0%