BZOJ2820 YY的GCD <莫比乌斯反演>

Problem

YY的GCD

Description

神犇虐完数论后给出了一题：
给定，求且为质数的有多少对
这种必然不会了，于是向你来请教。
多组输入。

Input

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

Output

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

Sample Input

1
2
3

2
10 10
100 100

Sample Output

1
2

30
2791

HINT

标签：莫比乌斯反演

Solution

套路反演+积性函数预处理。

先套路推一波反演式：

那么我们需要用线筛预处理出所有值。
对于当前预处理到的数和枚举到的质数，有

下面的式子的一部分可以化为上面的式子，剩余部分直接加上去。
分类讨论：

若，则下式中时，的分解式中的指数一定大于，于是只有时会对答案产生的贡献，所以。
若，则下式中对于任意，其贡献都为上式中对应项的贡献乘，即的贡献为。当时，只存在，此时贡献为。因此。

由此，可以线筛预处理出所有值，然后根号分块计算答案即可。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
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');
}
int pri[MAX_N+5], mu[MAX_N+5], fac[MAX_N+5], cnt;	bool NotPri[MAX_N+5];
void PriS() {
    mu[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1;
        for (int j = 0, x; j < cnt; j++) {
            if ((x = i*pri[j]) > MAX_N) break;
            NotPri[x] = true;
            if (i%pri[j]) mu[x] = -mu[i];
            else {mu[x] = 0;	break;}
        }
    }
}
int main() {
    int n;	read(n), PriS();	lnt ans = 0LL;
    for (lnt i = 1, l, r; i < sqrt(n); i++) {
        cnt = 0; for (int j = 1; j <= sqrt(i); j++) if (i%j == 0) fac[cnt++] = j;
        for (l = 1; l < i; l = r+1) {
            lnt val = n/(i*(i+l)); if (!val) break;	r = min(n/val/i-i, i-1);
            for (lnt k = 0, j; k < cnt; k++) {
                j = fac[k], ans += mu[j]*(r/j-(l-1)/j)*val;	lnt t = i/j;
                if (i%t == 0 && (j^t)) ans += mu[t]*(r/t-(l-1)/t)*val;
            }
        }
    }
    return printf("%lld\n", ans), 0;
}