题外话:好像文章有点长,本地调的时候加载目录都掉帧了。虽然一度想删点题目,但思前想后还是一题没删,总感觉每一题都代表了一种典型,实在不好取舍,或许只写推导会好一点,但还是有点怕代码的实现未有较好交代。。。

好了,闲言少叙。 本篇是平时刷的反演题目的解题记录,个人认为这方面的知识点和写题目是有点脱节的,题目要么是纯套路,要么就是有些不太友好的小技巧。

题目来源:Luogu, LibreOJ, HDU等。


P3312 [SDOI2014]数表

题目描述

有一张 $n\times m$ 的数表,其第 $i$行第 $j$ 列($1\le i\le n$,$1\le j\le m$)的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$,计算数表中不大于 $a$ 的数之和。

输入包含多组数据。

输入的第一行一个整数 $Q$ 表示测试点内的数据组数

接下来 $Q$ 行,每行三个整数 $n$,$m$,$a$($|a|\le 10^9$)描述一组数据。

答案模$2^{31}$。

显然有答案为:

$$Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma(\gcd(i,j))[\gcd(i,j)\leq a] \newline$$

先不考虑大小限制,之后将其转换成离线求值+动态加入贡献的问题。

$$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}\sigma(\gcd(i,j))&=\sum_{d=1}^{n}\sigma(d)\sum_{i=1}^{[\frac{n}{d}]}\sum_{j=1}^{[\frac{m}{d}]}[\gcd(i,j)=1]\newline &=\sum_{d=1}^{n}\sigma(d)\sum_{k=1}^{[\frac{n}{d}]}\mu(k)\sum_{i=1}^{[\frac{n}{d}]}\sum_{j=1}^{[\frac{m}{d}]}\newline &=\sum_{d=1}^{n}\sigma(d)\sum_{k=1}^{[\frac{n}{d}]}\mu(k)[\frac{n}{dk}]\times[\frac{m}{dk}]\newline &=\sum_{T=1}^{n}[\frac{n}{T}][\frac{m}{T}]\sum_{d\mid T}\sigma(d)\mu(\frac{T}{d}) \end{aligned}$$

只有当$\sigma(n)\leq a_i$,才将$\sigma(n)$的贡献计入,那么我们可以离线处理,用树状数组维护,$O(Q\sqrt{n}\log{n})$。

取模$2^{31}$标志着需要$32$位整型自然溢出,当然最终还是要变成无符号整数,这里可以写成ans & 2^{31}-1

 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
#include <bits/stdc++.h>
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;

typedef long long i64;

const int N = 1e5;
const int mod = 0x7fffffff;

int T;
struct Query {
	int n, m, a, id;
	bool operator < (const Query &b) const {
		return a < b.a;
	}
} Q[N + 10];
int ans[N + 10];
PII  s[N + 10];
int mu[N + 10];

bitset<N + 10> ok;
int pr[N], cnt;
int sig[N + 10], pw[N + 10];

void init(int n) {
	mu[1] = sig[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!ok[i]) mu[pr[++cnt] = i] = -1, sig[i] = i + 1, pw[i] = i;
		for (int j = 1; j <= cnt && pr[j] <= n / i; ++j) {
			int t = pr[j] * i; ok[t] = 1;
			if (i % pr[j] == 0) {
				pw[t] = pw[i] * pr[j];
				sig[t] = 1LL * sig[i] * (pw[t] * pr[j] - 1) / (pw[t] - 1);
				break;
			}
			mu[t] = -mu[i], sig[t] = sig[i] * (pr[j] + 1), pw[t] = pr[j];
		}
	}
	for (int i = 1; i <= n; i++) s[i].fi = sig[i], s[i].se = i;
	sort(s + 1, s + 1 + n);
}

int tr[N + 10];
inline void ins(int p, int v) {
	for (; p <= N; p += p & -p) tr[p] += v;
}
inline int que(int p, int r = 0) {
	for (; p; p &= p - 1) r += tr[p];
	return r;
}

inline int slove(int n, int m, int res = 0) {
	if (n > m) n ^= m ^= n ^= m;
	for (int l = 1, r; l <= n; l = r + 1) {
		int fn = n / l, fm = m / l;
		r = min(n / fn, m / fm);
		res += fn * fm * (que(r) - que(l-1));
	} return res;
}

int main() {
	init(N);

	scanf("%d", &T);
	for (int i = 1; i <= T; i++)
		scanf("%d%d%d", &Q[i].n, &Q[i].m, &Q[i].a), Q[i].id = i;
	sort(Q + 1, Q + 1 + T);
	for (int o = 1, k = 1; o <= T; o++) {
		while (k <= N && s[k].fi <= Q[o].a) {
			for (int d = s[k].se, sg = s[k].fi, i = d, t = 1; i <= N; i += d, ++t)
				ins(i, sg * mu[t]);
			k++;
		} ans[Q[o].id] = slove(Q[o].n, Q[o].m);
	}
	for (int i = 1; i <= T; i++) printf("%d\n", ans[i] & mod);
	return 0;
}

P3172 [CQOI2015]选数

题目大意

在$[L,H]$中依次选择$N$个数(可以重复),求使得这$N$个数的$gcd$为$K$的选法取模$1e9+7$。

对于 $100%$ 的数据,$1\le N,K\le 10^9$,$1\le L\le H\le 10^9$,$H-L\le 10^5$。

$$\begin{aligned} Ans&=\sum_{a_1=L}^{H}\sum_{a_2=L}^{H}\dots\sum_{a_N=L}^{H}\left[ (a_1,a_2,\dots,a_N)=K \right] \newline &=\sum_{a_1=\lceil \frac{L}{K} \rceil}^{\lfloor\frac{H}{K} \rfloor}\sum_{a_2=\lceil \frac{L}{K} \rceil}^{\lfloor \frac{H}{K} \rfloor}\dots\sum_{a_N=\lceil \frac{L}{K} \rceil}^{\lfloor \frac{H}{K} \rfloor}\left[ (a_1,a_2,\dots,a_N)=1\right] \newline &=\sum_{a_1=\lceil \frac{L}{K} \rceil}^{\lfloor\frac{H}{K} \rfloor}\sum_{a_2=\lceil \frac{L}{K} \rceil}^{\lfloor \frac{H}{K} \rfloor}\dots\sum_{a_N=\lceil \frac{L}{K} \rceil}^{\lfloor \frac{H}{K} \rfloor}\sum_{d\mid(a_1,a_2,\dots,a_N)}{\mu(d)} \newline &=\sum_{d=1}^{\lfloor \frac{H}{K} \rfloor}{\mu(d)\times(\lfloor\frac{\lfloor\frac{H}{K} \rfloor}{d}\rfloor-\lceil\frac{\lceil\frac{L}{K}\rceil}{d}\rceil+1)^N}\newline \end{aligned}$$ 前者求$\sum\mu(n)$用杜教筛就可以了,$O(n^{\frac{2}{3}})$。

后者明显是分块+快速幂,但是里面存在一个向上取整的部分。想了很久怎样找向上取整的区间,然后突然记起向上取整可以转化为向下取整,即$\lceil \frac{L}{K} \rceil=\lfloor \frac{L-1}{K} \rfloor + 1$。 $$Ans=\sum_{d=1}^{\lfloor \frac{H}{K} \rfloor}{\mu(d)\times(\lfloor\frac{\lfloor\frac{H}{K} \rfloor}{d}\rfloor-\lfloor\frac{\lfloor\frac{L-1}{K}\rfloor}{d}\rfloor)^N}\newline$$

然后就和常规的整除分块一样啦。

 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
#include <bits/stdc++.h>
using namespace std;

const int N   = 1e6;
const int mod = 1e9 + 7;

int pr[N], cnt;
bitset<N + 10> ok;
int mu[N + 10];

void init(int n) {
	mu[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!ok[i]) mu[pr[++cnt] = i] = mod - 1;
		for (int j = 1; j <= cnt && pr[j] <= n / i; ++j) {
			ok[pr[j] * i] = 1;
			if (i % pr[j] == 0) break;
			mu[pr[j] * i] = mod - mu[i];
		}
	}
	for (int i = 1; i <= n; i++)
		mu[i] = (mu[i] + mu[i-1]) % mod;
	return ;
}

inline int qpow(int x, int n, int r = 1) {
	for (; n; n >>= 1, x = 1LL * x * x % mod)
		if (n & 1) r = 1LL * r * x % mod;
	return r;
}

unordered_map<int, int> sm;

inline int sieve(int n) {
	if (n <= N) return mu[n];
	if (sm.count(n)) return sm[n];
	int res = 1;
	for (int l = 2, r; l <= n; l = r + 1) {
		int fl = n / l; r = n / fl;
		res = (res - 1LL * sieve(fl) * (r - l + 1) % mod + mod) % mod;
	} return sm[n] = res;
}

int main() {
	init(N);

	int n, k, L, H;
	scanf("%d%d%d%d", &n, &k, &L, &H);
	H = H / k, L = (L - 1) / k;

	int ans = 0;
	for (int l = 1, r; l <= H; l = r + 1) {
		int fl = L / l, fh = H / l;
		fl ? r = min(H / fh, L / fl) : r = H / fh;
		ans = (ans + 1LL * (sieve(r) - sieve(l-1) + mod) * qpow(fh - fl, n) % mod) % mod;
	} printf("%d", ans);
	return 0;
}

P3911 最小公倍数之和

题目描述

对于$A_1,A_2,\cdots,A_N$,求 $\sum_{i=1}^N\sum_{j=1}^N lcm(A_i,A_j)$。

数据范围

$1\le N \le 50000;1 \le A_i \le 50000。$

随机数组的形式没办法直接快速求值,注意到,$A_i$的取值范围很小,我们可以定义一个贡献,将未出现的数剔除掉,只统计数组中元素的贡献。显然,这里应该用出现次数作为贡献(出现多少次就会被计算多少次)。 $$\begin{aligned} Ans&=\sum_{i=1}^{M}\sum_{j=1}^{M}lcm(i,j)\times c[i]\times c[j]\newline &=\sum_{g=1}^{M}\sum_{i=1}^{[\frac{M}{g}]}\sum_{j=1}^{[\frac{M}{g}]}{g\times i\times j}\times[(i,j)=1]\times c[ig]\times c[jg]\newline &=\sum_{g=1}^{M}\sum_{k=1}^{[\frac{M}{g}]}\mu(k)\sum_{i=1}^{[\frac{M}{gk}]}\sum_{j=1}^{[\frac{M}{gk}]}{g\times ik\times jk}\times c[igk]\times c[jgk]\newline &=\sum_{T=1}^{M}T(\sum_{i=1}^{[\frac{M}{T}]}i\times c[iT])^2\sum_{k \mid T}{k\times\mu(k)}\newline \end{aligned}$$ 后面一项可以预处理,中间项只能暴力去做,正好$M$不大,时间复杂度$O(M\log M)$能过。

 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
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int N = 5e4;

int n;

bitset<N + 10> ok;
int mu[N + 10], pr[N], cnt;
i64 s[N + 10], c[N + 10];

void init() {
	mu[1] = 1;
	for (int i = 2; i <= N; i++) {
		if (!ok[i]) mu[pr[++cnt] = i] = -1;
		for (int j = 1; j <= cnt && pr[j] <= N / i; ++j) {
			ok[pr[j] * i] = 1;
			if (i % pr[j] == 0) break;
			mu[pr[j] * i] = -mu[i];
		}
	}
	for (int i = 1; i <= N; i++) {
		i64 t = (i64)i * mu[i];
		for (int j = i; j <= N; j += i) s[j] += t;
	} return ;
}

int main() {
	init();

	scanf("%d", &n);
	for (int a, i = 1; i <= n; i++)
		scanf("%d", &a), ++c[a];
	i64 ans = 0;
	for (int i = 1; i <= N; i++) {
		i64 t = 0;
		for (int j = 1, m = N / i; j <= m; j++)
			t += (i64)j * c[i * j];
		ans = ans + (i64)i * t * t * s[i];
	} printf("%lld", ans);
	return 0;
}

P1829 [国家集训队]Crash的数字表格 / JZPTAB

题目描述

求$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)\mod 20101009$,其中$1<n,m\leq10^7$。

上面推过了,只要将贡献设置为$1$,得到答案: $$Ans=\sum_{T=1}^{n}T(\sum_{i=1}^{[\frac{n}{T}]}i)(\sum_{j=1}^{[\frac{m}{T}]}j)\sum_{k \mid T}{k\times\mu(k)}\newline$$ 看起来最终求值可以$O(\sqrt n)$解决,但是预处理的复杂度$O(n\log n)$太大了,需要优化。

首先,由于$\sum_{d\mid n}f(d)\mu(d)=\prod\limits_{p\mid n,p\in Prime}\left(1-f(p)\right)$,我们得到:

$$\sum_{k \mid T}{k\times\mu(k)}=\prod\limits_{p\mid n,p\in Prime}(1-p)$$

整体妥妥的积性,线性筛预处理就好了,我们将其令为$f(T)$,有 $$Ans=\sum_{T=1}^{n}T\times f(T)\times (\sum_{i=1}^{[\frac{n}{T}]}i)(\sum_{j=1}^{[\frac{m}{T}]}j)$$ 分块求值,$O(n+\sqrt n)$。

 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
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int mod = 20101009;
const int N = 1e7;

int pr[664579 + 10], cnt;
bitset<N + 10> ok;
int f[N + 10];

void init(int n) {
	f[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!ok[i]) f[pr[++cnt] = i] = mod + 1 - i;
		for (int j = 1; j <= cnt && pr[j] <= n / i; ++j) {
			ok[pr[j] * i] = 1;
			if (i % pr[j] == 0) {f[pr[j] * i] = f[i]; break;}
			f[pr[j] * i] = 1LL * f[i] * f[pr[j]] % mod;
		}
	} 
	for (int i = 1; i <= n; i++) f[i] = (f[i-1] + 1LL * f[i] * i % mod) % mod;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	if (n > m) n ^= m ^= n ^= m;
	init(n); //
	int ans = 0;
	for (int l = 1, r; l <= n; l = r + 1) {
		int fn = n / l, fm = m / l;
		r = min(n / fn, m / fm);
		fn = (1LL * fn * (fn + 1) >> 1LL) % mod;
		fm = (1LL * fm * (fm + 1) >> 1LL) % mod;
		ans = (ans + 1LL * fn * fm % mod * (f[r] - f[l-1] + mod) % mod) % mod;
	} printf("%d", ans);
	return 0;
}

当然,如果你推到之前一步就停下来开始码也能写,只是会慢大概150ms。 $$Ans=\sum_{g=1}^{n}g\sum_{k=1}^{[\frac{n}{g}]}k^2\mu(k)\sum_{i=1}^{[\frac{n}{gk}]}\sum_{j=1}^{[\frac{m}{gk}]}i\times j$$

现在,能两次整除分块解决啦。

 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
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 1e7 + 10;
const int mod  = 20101009;

int T, R;

int pr[664579 + 10], cnt;
bitset<maxn> ok;
int mu[maxn], f[maxn];

void init(int n) {
	mu[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!ok[i]) pr[++ cnt] = i, mu[i] = -1;
		for (int j = 1; j <= cnt && pr[j] <= n / i; j++) {
			ok[pr[j] * i] = 1;
			if (i % pr[j] == 0) break;
			mu[pr[j] * i] = -mu[i];
		}
	}
	for (int i = 1; i <= n; i++) {
		f[i] = (f[i-1] + 1LL * i * i * mu[i] % mod + mod) % mod;
	}
}

il int func(ll be, ll ed) { return (1LL * (be + ed) * (ed - be + 1) >> 1LL) % mod; }

int main() {
	int n, m, ans = 0;
	scanf("%d%d", &n, &m);
	int o = n < m ? n : m;
	init(o);
	for (int l = 1, r; l <= o; l = r + 1) {
		int ta = n / (n / l), tb = m / (m / l);
		r = ta < tb ? ta : tb;
		int sum = 0;
		for (int i = 1, j; i <= o / l; i = j + 1) {
			ta = (n / l) / ((n / l) / i), tb = (m / l) / ((m / l) / i); 
			j = ta < tb ? ta : tb;
			sum = (sum + 1LL * (f[j] - f[i-1] + mod) * func(1, n / l / i) % mod * func(1, m / l / i) % mod) % mod;
		}
		ans = (ans + 1LL * sum * func(l, r) % mod) % mod;
	}
	printf("%d", ans);
	return 0;
}

P2398 GCD SUM

题目描述

给定$n,m$,求$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)$.

数据范围

$n\leq1e5$

用一个之前没写过的欧拉反演,原理:$\sum_{d\mid n}\varphi(d)=n$。

$$\begin{aligned} Ans&=\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)\newline &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid\gcd(i,j)}\varphi(d)\newline &=\sum_{d=1}^{n}\varphi(d)\times[\frac{n}{d}]\times[\frac{m}{d}] \end{aligned}$$ 总共$O(n+\sqrt{n})$,数据范围给得太小了。

用莫反推起来步骤一样,就略去了。

 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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

bitset<N + 10> ok;
int pr[N], cnt;
long long phi[N + 10];
void init(int n) {
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!ok[i]) phi[pr[++cnt] = i] = i - 1;
		for (int j = 1; j <= cnt && pr[j] <= n / i; j++) {
			int t = pr[j] * i; ok[t] = 1;
			if (i % pr[j] == 0) {phi[t] = phi[i] * pr[j]; break;}
			phi[t] = phi[i] * phi[ pr[j] ];
		}
	}
	for (int i = 1; i <= n; i++) phi[i] += phi[i-1];
}

int main() {
	int n; scanf("%d", &n); init(n);
	long long ans = 0;
	for (int l = 1, r; l <= n; l = r + 1) {
		int fn = n / l;
		r = n / fn;
		ans += ( phi[r] - phi[l-1] ) * fn * fn;
	}
	printf("%lld", ans);
	return 0;
}

P2257 YY的GCD

题目描述

给定正整数 $n$,求 $1\le x \leq N,1 \le y \le M$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

数据范围

$T$组输入。(时间:4.00s

$T=1e4$,$N,M\leq1e7$。

$$\begin{aligned} Ans&=\sum_{x=1}^{N}\sum_{y=1}^{M}[(x,y)=p \land p\in Prime]\newline &=\sum_{p\in Prime}\sum_{x=1}^{[\frac{N}{p}]}\sum_{y=1}^{[\frac{M}{p}]}[(x,y)=1]\newline &=\sum_{p\in Prime}\sum_{k=1}^{[\frac{N}{p}]}\mu(k)\times[\frac{N}{pk}]\times[\frac{M}{pk}]\newline &=\sum_{T=1}^{N}[\frac{N}{T}]\times[\frac{M}{T}]\sum_{p\mid T,p\in Prime}\mu(\frac{T}{p}) \end{aligned}$$

$O(N+\pi(N)\log p)$预处理后面部分$F(n)=\sum\limits_{p\mid n,p\in Prime}\mu(\frac{n}{p})$。

(用线性筛可以优化到$O(N)$预处理) $$F(n)= \begin{cases} 1 & \textrm{if } n\in Prime \newline \mu(\frac{n}{p}) - F(\frac{n}{p}) & \textrm{if } p\mid\mid n\newline \mu(\frac{n}{p}) & \textrm{otherwise} \end{cases} $$

然后$O(T\sqrt N)$求值。

 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
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;

const int N = 1e7;

int pr[N], cnt;
bitset<N + 10> ok;
i64 F[N + 10], mu[N + 10];

void init(int n) {
	mu[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!ok[i]) mu[pr[++ cnt] = i] = -1, F[i] = 1;
		for (int j = 1; j <= cnt && pr[j] <= n / i; j++) {
			int t = pr[j] * i; ok[t] = 1;
			if (i % pr[j] == 0) {F[t] = mu[i];break;}
			mu[t] = -mu[i], F[t] = mu[i] - F[i];
		}
	}
	for (int i = 1; i <= n; i++) F[i] += F[i-1];
}

inline i64 slove(int n, int m, i64 res = 0) {
	if (n > m) n ^= m ^= n ^= m;
	for (int l = 1, r; l <= n; l = r + 1) {
		int fn = n / l, fm = m / l;
		r = min(n / fn, m / fm);
		res += 1LL * fn * fm * (F[r] - F[l-1]);
	} return res;
}

int main() {
	init(N);

	int T, n, m;
	for (scanf("%d", &T); T--; ) {
		scanf("%d%d", &n, &m);
		printf("%lld\n", slove(n, m) );
	}
	return 0;
}

「SDOI2015」约数个数和

题目描述

求$\sum_{i=1}^{N}\sum_{j=1}^{M}d(i,j)$

数据范围

多组,$1\leq T\leq 5e4$,$1\leq N,M,\leq 5e4$。

$$\begin{aligned} Ans&=\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]\newline &=\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{x\mid i}\sum_{y\mid j}\sum_{k\mid\gcd(x,y)}\mu(k)\newline &=\sum_{k=1}^{N}\mu(k)\times\left( \sum_{x=1}^{[\frac{N}{k}]}\sum_{i=1}^{[\frac{N}{kx}]}1 \right)\times\left( \sum_{y=1}^{[\frac{M}{k}]}\sum_{j=1}^{[\frac{M}{ky}]}1 \right)\newline &=\sum_{k=1}^{N}\mu(k)\times\left(\sum_{x=1}^{[\frac{N}{k}]}[\frac{N}{kx}]\right)\times\left(\sum_{y=1}^{[\frac{M}{k}]}[\frac{M}{ky}]\right) \end{aligned}$$

后面部分令为$F(\lfloor\frac{n}{k}\rfloor)=\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\lfloor\frac{n}{kx}\rfloor=\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\lfloor\frac{\lfloor\frac{n}{k}\rfloor}{x}\rfloor$。

明显的整除分块,$O(n\sqrt n)$预处理就完事了。

 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
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;

const int N = 5e4;

int pr[N], cnt;
bitset<N + 10> ok;
i64 F[N + 10], mu[N + 10];

void init(int n) {
	mu[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!ok[i]) mu[pr[++ cnt] = i] = -1;
		for (int j = 1; j <= cnt && pr[j] <= n / i; j++) {
			ok[pr[j] * i] = 1;
			if (i % pr[j] == 0) break;
			mu[pr[j] * i] = -mu[i];
		}
	}
	for (int i = 1; i <= n; i++) mu[i] += mu[i-1];
	for (int i = 1; i <= n; i++) {
		for (int l = 1, r; l <= i; l = r + 1) {
			int fn = i / l;
			r = i / fn;
			F[i] += 1LL * (r - l + 1) * fn;
		}
	}
}

inline i64 slove(int n, int m, i64 res = 0) {
	if (n > m) n ^= m ^= n ^= m;
	for (int l = 1, r; l <= n; l = r + 1) {
		int fn = n / l, fm = m / l;
		r = min(n / fn, m / fm);
		res += F[fn] * F[fm] * (mu[r] - mu[l-1]);
	} return res;
}

int main() {
	init(N);

	int T, n, m;
	for (scanf("%d", &T); T--; ) {
		scanf("%d%d", &n, &m);
		printf("%lld\n", slove(n, m) );
	}
	return 0;
}

LCMSUM

题目描述

求$\sum_{i=1}^{n}lcm(i,n)$

数据范围

500ms

多组,$T\leq3e5,1\leq n\leq1e6$。

$$\begin{aligned} Ans&=\sum_{g\mid n}\sum_{i=1}^{\frac{n}{g}}i\times n\times[(i, \frac{n}{g})=1]\newline &=n\sum_{g\mid n}\sum_{i=1}^{\frac{n}{g}}i\times[(i,\frac{n}{g})=1]\newline &=n\sum_{g\mid n}\frac{\frac{n}{g}\times\varphi(\frac{n}{g})}{2} \end{aligned}$$

直接预处理就完事$O(n\ln n)$。

 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
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;

const int N = 1e6;

int n, m;
int pr[N], cnt;
bitset<N + 10> ok;
i64 f[N + 1], phi[N + 1];

void init(int n) {
	phi[1] = 2LL;
	for (int i = 2; i <= n; i++) {
		if (!ok[i]) phi[pr[++cnt] = i] = i - 1;
		for (int j = 1; j <= cnt && pr[j] <= n / i; ++j) {
			int t = pr[j] * i; ok[t] = 1;
			if (i % pr[j] == 0) {phi[t] = phi[i] * pr[j];break;}
			phi[t] = phi[i] * (pr[j] - 1);
		}
	}
	for (int i = 1; i <= n; i++) {
		i64 t = phi[i] * i;
		for (int j = i; j <= n; j += i) f[j] += t;
	}
}

int main() {
	init(N);

	int T; scanf("%d", &T);
	while (T--) {
		int n; scanf("%d", &n);
		printf("%lld\n", f[n] * n >> 1LL);
	}
	return 0;
}

[HDU 6134] Battlestation Operational

题目描述 求$\sum_{i=1}^{n}\sum_{j=1}^{i}\lceil\frac{i}{j}\rceil\times[(i,j)=1] \mod 1e9+7$。

数据范围

$1\leq n\leq 1e6$,多组(不超过$1e4$)

先考虑一个子问题,$g(n)=\sum_{i=1}^{n}\lceil\frac{n}{i}\rceil\times[(n,i)=1]$。 $$\begin{aligned} g(n)&=\sum_{i=1}^{n}\lceil\frac{n}{i}\rceil\times[(n,i)=1]\newline &=\sum_{d\mid n}\mu(d)\sum_{i=1}^{\frac{n}{d}}\lceil\frac{\frac{n}{d}}{i}\rceil\newline &=\sum_{d\mid n}\mu(d)\left(\frac{n}{d}-\sigma_0(\frac{n}{d})+\sum_{i=1}^{\frac{n}{d}}\lfloor\frac{\frac{n}{d}}{i}\rfloor\right)\newline &=\sum_{d\mid n}\mu(d)\left(\frac{n}{d}+\sum_{i=1}^{\frac{n}{d}-1}\sigma_0(i)\right) \end{aligned}$$

中间一步稍作解释吧, $$\sum_{i=1}^{n}\sigma_0(i)=\sum_{i=1}^{n}\sum_{d\mid i}1=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}1=\sum_{d=1}^{n}\lfloor\frac{n}{d}\rfloor$$。

其实现在已经能写了,初始化$\mu(n),\sigma_0(n)$就可以,这个方法比较常规就不写了。

我们可以继续使用莫比乌斯反演优化,$g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d})$,得到$f(n)=\sum_{d\mid n}g(d)$。

也就是$g(n)=f(n)-\sum_{d\mid n,d<n}g(d)$,直接推就好了也是$O(n\ln n)$,但是这样就不用预处理$\mu$了,借助滚动数组的思想我们还能进一步优化空间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
typedef long long i64;

const int N = 1e6;
const int mod = 1e9 + 7;

i64 g[N + 10], d[N + 10];

int main() {
	for (int i = 1; i <= N; i++) 
		for (int j = i; j <= N; j += i) 
			d[j]++;
	for (int i = 1; i <= N; i++) d[i] += d[i-1], d[i] %= mod;
	for (int i = 1; i <= N; i++) g[i] = (i + d[i-1]) % mod;
	for (int i = 1; i <= N; i++)
		for (int j = i << 1; j <= N; j += i)
			g[j] = (g[j] - g[i] + mod) % mod;
	for (int i = 1; i <= N; i++) g[i] += g[i-1], g[i] %= mod;
	int n; 
	while (~scanf("%d", &n)) printf("%lld\n", g[n]);
	return 0;
}