Luogu P6055 [RC-02] GCD（莫比乌斯反演，杜教筛）（这题乐死我了，真就图一乐呗）_繁凡さん的博客

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

Weblink

https://www.luogu.com.cn/problem/P6055

Problem

给出 N N N，求：

∑ i = 1 N ∑ j = 1 N ∑ p = 1 ⌊ N ȷ ⌋ ∑ q = 1 ⌊ N j ⌋ [ gcd ⁡ ( i , j ) = 1 ] [ gcd ⁡ ( p , q ) = 1 ] \sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{p=1}^{\left\lfloor\frac{N}{\jmath}\right\rfloor} \sum_{q=1}^{\left\lfloor\frac{N}{j}\right\rfloor}[\operatorname{gcd}(i, j)=1][\operatorname{gcd}(p, q)=1] i=1∑N​j=1∑N​p=1∑⌊ȷN​⌋​q=1∑⌊jN​⌋​[gcd(i,j)=1][gcd(p,q)=1]

答案模 998244353 998244353 998244353。

Solution

这题真是乐死我了，真就图一乐呗

上来怎么看这个 j j j 怎么不顺眼，这不先把 j j j 直接丢回去 ？？？

然后这题就没了…

随便反演一下，杜教筛随便搞搞就完事了

      ∑ i = 1 N ∑ j = 1 N ∑ p = 1 ⌊ N j ⌋ ∑ q = 1 ⌊ N j ⌋ [ gcd ⁡ ( i , j ) = 1 ] [ gcd ⁡ ( p , q ) = 1 ] = ∑ i = 1 N ∑ j = 1 N ∑ p = 1 N ∑ q = 1 N [ gcd ⁡ ( i , j ) = 1 ] [ gcd ⁡ ( p , q ) = j ] = ∑ i = 1 N ∑ p = 1 N ∑ q = 1 N [ gcd ⁡ ( i , p , q ) = 1 ] = ∑ i = 1 N ∑ p = 1 N ∑ q = 1 N ∑ d ∣ gcd ⁡ ( i , p , q ) μ ( d ) = ∑ d = 1 N ∑ i = 1 N ∑ p = 1 N ∑ q = 1 N [ d ∣ i ] [ d ∣ p ] [ d ∣ q ] μ ( d ) = ∑ d = 1 N ∑ i = 1 ⌊ N d ⌋ ∑ p = 1 ⌊ N d ⌋ ∑ q = 1 ⌊ N d ⌋ μ ( d ) = ∑ d = 1 N μ ( d ) ⌊ N d ⌋ 3 \begin{aligned} &\ \ \ \ \ \sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\left\lfloor\frac N j\right\rfloor}\sum_{q=1}^{\left\lfloor\frac 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_{i=1}^N\sum_{p=1}^{N}\sum_{q=1}^{N}\sum_{d\mid \gcd(i,p,q)}\mu(d)&\\& =\sum_{d=1}^N\sum_{i=1}^N\sum_{p=1}^{N}\sum_{q=1}^{N}[d\mid i][d\mid p][d\mid q]\mu(d)&\\& =\sum_{d=1}^N\sum_{i=1}^{\left\lfloor\frac N d\right\rfloor }\sum_{p=1}^{\left\lfloor\frac N d\right\rfloor }\sum_{q=1}^{\left\lfloor\frac N d\right\rfloor}\mu(d)&\\& =\sum_{d=1}^N\mu(d)\left\lfloor\frac N d\right\rfloor^3 \end{aligned} ​     i=1∑N​j=1∑N​p=1∑⌊jN​⌋​q=1∑⌊jN​⌋​[gcd(i,j)=1][gcd(p,q)=1]=i=1∑N​j=1∑N​p=1∑N​q=1∑N​[gcd(i,j)=1][gcd(p,q)=j]=i=1∑N​p=1∑N​q=1∑N​[gcd(i,p,q)=1]=i=1∑N​p=1∑N​q=1∑N​d∣gcd(i,p,q)∑​μ(d)=d=1∑N​i=1∑N​p=1∑N​q=1∑N​[d∣i][d∣p][d∣q]μ(d)=d=1∑N​i=1∑⌊dN​⌋​p=1∑⌊dN​⌋​q=1∑⌊dN​⌋​μ(d)=d=1∑N​μ(d)⌊dN​⌋3​​

%
时间复杂度 O ( n 2 3 ) O(n^{\frac 2 3}) O(n32​)。

20分钟水一道紫题 ^q^

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e6 + 7, mod = 998244353;

ll n, m, s, t;
ll ans;
int primes[maxn], cnt;
bool vis[maxn];
ll mu[maxn];
unordered_map <ll, ll> sum_mu;

void prework(int n)
{
	mu[1] = 1;
	for (int i = 2; i <= n; ++ i) {
		if(vis[i] == 0) {
			primes[ ++ cnt] = i;
			mu[i] = -1;
		}
		for (int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
			vis[i * primes[j]] = 1;
			if(i % primes[j] == 0) 
				break;
			mu[i * primes[j]] -= mu[i];
		}
	}
	for (int i = 1; i <= n; ++ i) {
		mu[i] += mu[i - 1];
	}
}

int g_sum(int x)
{
	return x;
}

inline int get_sum_mu(int x)
{
	if(x <= maxn - 10) return mu[x];
	if(sum_mu.find(x) != sum_mu.end()) return sum_mu[x];
	ll ans = 1;
	for (ll l = 2, r; l <= x; l = r + 1) {
		r = x / (x / l);
		ans -= (g_sum(r) - g_sum(l - 1)) * get_sum_mu(x / l);
	}
	return sum_mu[x] = ans / g_sum(1);
}

int main()
{
//	int ^q^; 
	prework(maxn - 7);
	t = 1;
	while(t -- ) {
		ans = 0;
		scanf("%lld", &n);
		for (ll l = 1, r = 0; l <= n; l = r + 1) {
			r = n / (n / l);
			ll _ = (n / l) * (n / l) % mod * (n / l) % mod; 
			ans = (ans + (get_sum_mu(r) - get_sum_mu(l - 1) + mod) % mod * _ % mod) % mod;
		}
		printf("%lld\n", ans);
	}
	return 0;
}