Bzoj2818 Gcd（莫比乌斯反演）

题面

题意都在题目里面了

题解

你可以把题意看成这个东西

$$ \sum_{i=1}^n\sum_{j=1}^m\mathbf f(gcd(i,j)) $$

其中$\mathbf f(n)$为$是否是一个质数[n是否是一个质数]$

然后把$\mathbf f$反演一下，找到一个$\mathbf g$令$\mathbf f=\mathbf 1 \ast \mathbf g$，即：

$$ \mathbf g(n)=\sum_{d\mid n}\mu(\frac nd)\cdot \mathbf f(d)=\sum_{d\mid n, d \in prime}\mu (\frac nd) $$

所以$\mathbf g$可以这样求：

for(int j = 1; j <= cnt; ++j)

    for(int i = 1; i * prime[j] <= n; ++i)

        g[i * prime[j]] += mu[i];

就是枚举系数。

接着考虑怎么做：

由于$gcd$有一个很好的性质：

$d\mid gcd(i,j) \Leftrightarrow d\mid i, d\mid j$

所以

$$ \sum_{i=1}^n\sum_{j=1}^n\sum_{d\mid i,d\mid j}\mathbf g(d) \\ =\sum_{d=1}^{min(n,m)}\mathbf g(d)\sum_{i=1}^n\sum_{j=1}^m[d\mid i][d\mid j] \\ =\sum_{d=1}^{min(n,m)}\mathbf g(d) \lfloor\frac nd \rfloor\lfloor\frac md\rfloor $$

然后就可以整除分块了！！

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::min; using std::max;

using std::swap; using std::sort;

typedef long long ll;

template<typename T>

void read(T &x) {

    int flag = 1; x = 0; char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int N = 1e7 + 10;

int t, n, m, mu[N], g[N], prime[N], cnt;

long long sum[N], ans; bool notprime[N];

void getmu(int k) {

	mu[1] = 1;

	for(int i = 2; i <= k; ++i) {

		if(!notprime[i]) prime[++cnt] = i, mu[i] = -1;

		for(int j = 1; j <= cnt && prime[j] * i <= k; ++j) {

			notprime[prime[j] * i] = true;

			if(!(i % prime[j])) break;

			mu[prime[j] * i] = -mu[i];

		}

	}

	for(int j = 1; j <= cnt; ++j)

		for(int i = 1; i * prime[j] <= k; ++i)

			g[i * prime[j]] += mu[i];

	for(int i = 1; i <= k; ++i)

		sum[i] = sum[i - 1] + 1ll * g[i];

}

int main () {

	read(n), getmu(n);

	for(int l = 1, r; l <= n; l = r + 1) {

		r = n / (n / l);

		ans += (sum[r] - sum[l - 1]) * (n / l) * (n / l);

	} printf("%lld\n", ans);

    return 0;

}