【NOI2016】循环之美题解

Solution

由数论基础知识答案即为$$\sum_{i = 1}^n\sum_{j = 1}^m[i \perp j][j \perp k]$$

莫反套路可化为$$\sum_{d = 1}\mu(d)[d \perp k] \lfloor \frac{n}{d} \rfloor \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}[j \perp k]$$

如果我们可以求出$g(x)=\sum_{i=1}^x [x \perp k]$，那么后面那坨东西就容易分块搞掉

然后我们惊奇的发现$g(n)=\lfloor \frac{n}{k} \rfloor g(k) + g(n\mod k)$

然后我们只需要求$f(n)=\sum_{i=1}^n \mu(i)[i \perp k]$的前缀和了

这一部分是本题难点。

发现

\[\begin{aligned}
f(n)&=\sum_{i=1}^n f(\lfloor \frac{n}{i} \rfloor)[i \perp k] - \sum_{i=2}^n f(\lfloor \frac{n}{i} \rfloor)[i \perp k] \\
&=\sum_{i=1}^n \sum_{j=1}^{\lfloor \frac{n}{i} \rfloor} \mu(j) [ij \perp k] - \sum_{i=2}^n f(\lfloor \frac{n}{i} \rfloor)[i \perp k]\\
&=\sum_{T=1}^n [T \perp k] \sum_{d | k}\mu(d) - \sum_{i=2}^n f(\lfloor \frac{n}{i} \rfloor)[i \perp k] \\
&=1 - \sum_{i=2}^n f(\lfloor \frac{n}{i} \rfloor)[i \perp k]
\end{aligned}
\]

至此，我们成功构造出了杜教筛式子。

问题迎刃而解。

Code

#include <cstdio>

#include <iostream>

#include <map>

#define LL long long

using namespace std;

inline LL read() {

	LL res = 0; char ch = getchar();

	for(; !isdigit(ch); ch = getchar());

	for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);

	return res;

}

int n, k, vis[3000000], p[3000000], cnt, g[3000000], m, mu[3000000], f[3000000];

LL ans;

void Sieve() {

	mu[1] = 1;

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

		if(!vis[i]) p[++cnt] = i, mu[i] = -1;

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

			vis[i * p[j]] = 1;

			if(i % p[j] == 0) break;

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

		}

	}

}

int gcd(int x, int y) {return (y == 0) ? x : gcd(y, x % y);}

map <int, LL> re;

void Init() {

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

		g[i] = g[i - 1];

		if(gcd(i, k) == 1) ++ g[i];

	}

	for(int i = 1; i <= 2000000; ++i) {

		f[i] = f[i - 1];

		if(gcd(i, k) == 1) f[i] += mu[i];

	}

	return ;

}

LL G(int x, int y) {return x / y * g[y] + g[x % y];}

LL F(int x) {

	if(x <= 2000000) return f[x];

	if(re.find(x) != re.end()) return re[x];

	LL res = 1;

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

		r = x / (x / l);

		res -= F(x / l) * (G(r, k) - G(l - 1, k));

	}

	return re[x] = res;

}

int main() {

	n = read(), m = read(), k = read();

	Sieve();

	Init();

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

		r = min(n / (n / l), m / (m / l));

		ans = ans + 1ll * (F(r) - F(l - 1)) * (n / l) * G(m / l, k);

	}

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

}