题解 P6055 【[RC-02] GCD】

\[ans=\sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\left\lfloor\dfrac{N}{j}\right\rfloor}\sum_{q=1}^{\left\lfloor\dfrac{N}{j}\right\rfloor}[gcd(i,j)=1][gcd(p,q)=1] \]

方法1：

\[\begin{aligned} ans & = \sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\left\lfloor\dfrac{N}{j}\right\rfloor}\sum_{q=1}^{\left\lfloor\dfrac{N}{j}\right\rfloor}[gcd(i,j)=1][gcd(p,q)=1] \\ & = \sum_{i=1}^{N}\sum_{j=1}^N\sum_{p=1}^{N}\sum_{q=1}^N[gcd(i,j)=1][gcd(p,q)=j] \\ & = \sum_{i=1}^N\sum_{p=1}^{N}\sum_{q=1}^N[gcd(i,p,q)=1] \\ & = \sum_{d=1}^N\mu(d)\left\lfloor\dfrac{N}{d}\right\rfloor^3 \end{aligned} \]

方法2:

\[\begin{aligned} ans & =\sum_{i=1}^{N}\sum_{j=1}^N(\sum_{d|gcd(i,j)}\mu(d))(\sum_{p=1}^{\left\lfloor\dfrac{N}{j}\right\rfloor}\sum_{q=1}^{\left\lfloor\dfrac{N}{j}\right\rfloor}\sum_{t|gcd(p,q)}\mu(t)) \\ & =\sum_{i=1}^{N}\sum_{j=1}^N(\sum_{d|gcd(i,j)}\mu(d))(\sum_{t=1}^{\left\lfloor\dfrac{N}{j}\right\rfloor}\mu(t)\left\lfloor\dfrac{N}{jt}\right\rfloor^2) \\ & =\sum_{d=1}^N\mu(d)\left\lfloor\dfrac{N}{d}\right\rfloor\sum_{j=1}^{\left\lfloor\dfrac{N}{d}\right\rfloor}1\cdot\sum_{t=1}^{\left\lfloor\dfrac{N}{d}\right\rfloor}\left\lfloor\dfrac{N}{dt}\right\rfloor^2\sum_{g|t}\mu(t) \\ & =\sum_{d=1}^N\mu(d)\left\lfloor\dfrac{N}{d}\right\rfloor\sum_{j=1}^{\left\lfloor\dfrac{N}{d}\right\rfloor}1\cdot\sum_{t=1}^{\left\lfloor\dfrac{N}{d}\right\rfloor}\left\lfloor\dfrac{N}{dt}\right\rfloor^2[t=1] \\ & =\sum_{d=1}^N\mu(d)\left\lfloor\dfrac{N}{d}\right\rfloor\sum_{j=1}^{\left\lfloor\dfrac{N}{d}\right\rfloor}1\cdot\left\lfloor\dfrac{N}{d}\right\rfloor^2 \\ & =\sum_{d=1}^N\mu(d)\left\lfloor\dfrac{N}{d}\right\rfloor^3 \end{aligned} \]

然后数论分块+杜教筛即可

#include
#include
#define Starseven main
#define ll long long
const int N = 8e6;
const ll mod = 998244353;
int prime[N + 20], num;
ll mu[N + 20];
bool vis[N + 20];
std::map mp;

void Init() {
	mu[1] = 1;
	for (int i = 2; i <= N; i++) {
		if(!vis[i]) {
			prime[++num] = i;
			mu[i] = -1ll;
		}
		for (int j = 1; j <= num && prime[j] * i <= N; j++) {
			int x = prime[j] * i;
			vis[x] = true;
			if(i % prime[j] == 0) {
				mu[x] = 0;
				break;
			}
			mu[x] = -mu[i];
		}
	}
	for (int i = 1; i <= N; i++) {
		mu[i] += mu[i - 1];
	} 
	return ;
}

ll Get_sum(ll x) {
	if(x <= N) return mu[x];
	if(mp[x]) return mp[x];
	ll re = 1;
	for (ll l = 2, r; l <= x; l = r + 1) {
		r = x / (x / l);
		re = (re - (r - l + 1) * Get_sum(x / l)) % mod;
		re = (re + mod) % mod;
	}
	mp[x] = re;
	return re;
}

int Starseven(void) {
	ll n;
	read(n);
	Init();
	ll ans = 0;
	for (ll l = 1, r; l <= n; l = r + 1) {
		ll hack = n / l;
		r = n / (n / l);
		hack = hack * hack % mod * hack % mod;
		ans = (ans + (Get_sum(r) - Get_sum(l - 1)) % mod * hack % mod) % mod;
		ans = (ans + mod) % mod;
	}
	write(ans);
	puts(""); 
	return 0;	
}
数论莫比乌斯反演|杜教筛

相关

「笔记」数论知识整理

【数论】【差分】Row GCD

快速数论变换（NTT）

ABC222 G - 222（数论）

数论的一些简单定理证明

数论基础（素数筛选）

[CF615D] Multipliers - 数论

[CF1493D] GCD of an Array - 数论,map,set

【题解】BZOJ-4176 Lucas的数论

简单数论：最大公因数与最小公倍数问题

【初等数论】乘法逆元略解

数论-孙子定理（中国剩余定理）及应用

标签