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;
}