【luogu 1457】在表格里造序列（莫反）（杜教筛）

在表格里造序列

题目链接：luogu 1457

题目大意

有一个 n*n 的表格，每个位置有一些数列，其中 i 行 j 列里面的数列是所有满足长度为 m，值域是 1~n，且所有值的 gcd 与 i,j 的 gcd 相同的数组。
问你表格里总共有多少个数组。

思路

${}_{{}_{{}_{害，世界上最好的还得是莫反。}}}$
${}_{{}_{{}_{当其它所有的题都在用奇奇怪怪的方式恶心你的时候}}}$
${}_{{}_{{}_{只有莫反，纯纯的推式子，纯纯的，多好啊。}}}$
${}_{{}_{{}_{（}}}$
${}_{{}_{{}_{还有捏嘛csp怎么不考数学（算了考了我也不会，还是别考了吧}}}$

---

考虑枚举 $\gcd$ 的值，再分别枚举由多少个数组以及多少个表格上的位置满足条件。
$\sum _{d=1}^n(\sum _{x=1}^n\sum _{y=1}^n[\gcd (x,y)=d])(\sum _{a_1=1}^n...\sum _{a_m=1}^n[\gcd (a_1,...,a_m=d)])$
$\sum _{d=1}^n(\sum _{x=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{y=1}^{\lfloor \frac{n}{d}\rfloor }[\gcd (x,y)=1])(\sum _{a_1=1}^{\lfloor \frac{n}{d}\rfloor }...\sum _{a_m=1}^{\lfloor \frac{n}{d}\rfloor }[\gcd (a_1,...,a_m=1)])$
$\sum _{d=1}^n(\sum _{x=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{y=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{p|\gcd (x,y)}\mu (p))(\sum _{a_1=1}^{\lfloor \frac{n}{d}\rfloor }...\sum _{a_m=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{p|\gcd (a_1,...,a_m)}\mu (p))$
$\sum _{d=1}^n(\sum _{p=1}^{\lfloor \frac{n}{d}\rfloor }\mu (p)\sum _{x=1}^{\lfloor \frac{n}{dp}\rfloor }\sum _{y=1}^{\lfloor \frac{n}{dp}\rfloor })(\sum _{p=1}^{\lfloor \frac{n}{d}\rfloor }\mu (p)\sum _{a_1=1}^{\lfloor \frac{n}{dp}\rfloor }...\sum _{a_m=1}^{\lfloor \frac{n}{dp}\rfloor })$
$\sum _{d=1}^n(\sum _{p=1}^{\lfloor \frac{n}{d}\rfloor }\mu (p)(\lfloor \frac{n}{dp}\rfloor {)}^2)(\sum _{p=1}^{\lfloor \frac{n}{d}\rfloor }\mu (p)(\lfloor \frac{n}{dp}\rfloor {)}^m)$

$\sum _{d=1}^n\sum _{p=1}^{\lfloor \frac{n}{d}\rfloor }\mu (p)(\lfloor \frac{n}{dp}\rfloor {)}^m=n^m$
$\sum _{p=1}^n\mu (p)(\lfloor \frac{n}{p}\rfloor {)}^m=n^m-\sum _{d=2}^n\sum _{p=1}^{\lfloor \frac{n}{d}\rfloor }\mu (p)(\lfloor \frac{n}{dp}\rfloor {)}^m$
设 $\sum _{p=1}^n\mu (p)(\lfloor \frac{n}{p}\rfloor {)}^m=f_n$

$f_n=n^m-\sum _{d=2}^n{f}_{\lfloor \frac{n}{d}\rfloor }$

$\sum _{d=1}^n(\sum _{p=1}^{\lfloor \frac{n}{d}\rfloor }\mu (p)(\lfloor \frac{n}{dp}\rfloor {)}^2)(f_{\lfloor \frac{n}{d}\rfloor })$

其中 $f$ 可以记忆化一下在常规整除分块做到 $O(n^{\frac{3}{4}})$，左边的一坨式子，都可以用杜教筛快速 rush $\mu$ 前缀和也是 $O(n^{\frac{3}{4}})$ 从而通过题目捏。

代码

#include
#include
#define ll long long
#define mo 998244353

using namespace std;

const int Lim = 1e6;
const int B = 2e5 + 100;
ll n, m, lim, mus[Lim + 100];
ll rem_f[B], rem_mu[B], prime[Lim + 100];
bool np[Lim + 100];

int id(ll x) {
	if (x <= lim) return x; return lim + n / x;
}

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % mo;
		x = x * x % mo; y >>= 1;
	}
	return re;
}

ll get_f(ll now) {
	if (rem_f[id(now)] != -1) return rem_f[id(now)];
	ll re = ksm(now, m);
	for (ll L = 2, R; L <= now; L = R + 1) {
		R = now / (now / L);
		(re += mo - (R - L + 1) % mo * get_f(now / L) % mo) %= mo;
	}
	return rem_f[id(now)] = re;
}

ll ask(ll now) {
	if (now <= Lim) return (mus[now] % mo + mo) % mo;
	if (rem_mu[id(now)] != -1) return rem_mu[id(now)];
	ll re = 1;
	for (int L = 2, R; L <= now; L = R + 1) {
		R = now / (now / L);
		(re += mo - (R - L + 1) * ask(now / L) % mo) %= mo;
	}
	return rem_mu[id(now)] = re;
}

ll slove(ll n) {
	ll ans = 0;
	for (ll L = 1, R; L <= n; L = R + 1) {
		R = n / (n / L);
		ll mus = (ask(R) - ask(L - 1) + mo) % mo;
		(ans += mus * (n / L) % mo * (n / L) % mo) %= mo;
	}
	return ans;
}

int main() {
	for (int i = 0; i < B; i++) rem_f[i] = rem_mu[i] = -1;
	mus[1] = 1;
	for (int i = 2; i <= Lim; i++) {
		if (!np[i]) mus[i] = -1, prime[++prime[0]] = i;
		for (int j = 1; j <= prime[0] && i * prime[j] <= Lim; j++) {
			np[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
				else mus[i * prime[j]] = -mus[i];
		}
		mus[i] += mus[i - 1];
	}
	
	scanf("%lld %lld", &n, &m); lim = sqrt(n);
	
	ll ans = 0;
	for (ll L = 1, R; L <= n; L = R + 1) {
		R = n / (n / L);
		(ans += (R - L + 1) % mo * slove(n / L) % mo * get_f(n / L) % mo) %= mo;
	}
	printf("%lld", ans);
	
	return 0;
}
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81