P2398 GCD SUM 题解

算法一

对于 \(30 \%\) 的数据，\(n \leq 3 \times 10^3\).

直接模拟就好了。

时间复杂度：\(O(n^2 \log n)\). 实际得分：\(30pts\).

for(i from 1 to n)
for(j from 1 to n)
	s =gcd(i,j)
print(s)	

算法二

对于 \(60 \%\) 的数据，\(7000 \leq n \leq 7100\).

注意到 \(O(n^2 \log n)\) 无法通过了。但是，我们可以计算出 \(n = 7000\) 的答案为 \(275797760\). 然后，对于 \(7001\) ~ \(n\) 区间的答案，实际上就是 两倍的该区间与 \(1 \leq i \leq 7000\) 的两两 \(\gcd\) 之和，再加上自己和自己区间答案。

？？？

就比方说，\(a\) 和 \(b\) 表示区间，定义 \(a \times b\) 为 \(a\) 区间与 \(b\) 区间两两 \(\gcd\) 和。那么，\(x = a b\)，则 \(x^2 = (a b)^2 = a^2 2 \times a \times b b^2\).

而 \(a^2\) 的答案被提前算出，然后 \(b^2\) 区间长度 \(\leq 100\) 结束，\(a \times b\) 计算也只需要 \(7000 \times 100 = 7 \times 10^5\) 再加个 \(\log\) 的时间，过了。

时间复杂度：\(O(\text{wys})\). 实际得分：\(60pts\).

s=275797760
for(i from 1 to 7000)
for(j from 7001 to n)
	s =gcd(i,j)*2
for(i from 7001 to n)
for(j from 7001 to n)
	s =gcd(i,j)
print(s)		

算法三

显然本题可以用 \(\phi\) 过，但是我们用 莫比乌斯反演！

优化时间复杂度常常需要从零开始。 —— 《深入浅出程序设计竞赛 - 基础篇》 某句改编

对，下面是推式子时间。

\[\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j) \]

\[= \sum_{d=1}^n d \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)==d] \]

\[= \sum_{d=1}^n d \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} [\gcd(i,j)==1] \]

\[= \sum_{d=1}^n d \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{k|\gcd(i,j)} \mu_k \]

\[= \sum_{d=1}^n d \sum_{k=1}^n \lfloor \frac{n}{T} \rfloor^2 \mu_k (T = d \times k) \]

\[= \sum_{T=1}^n \sum_{d|T} d \times \mu_\frac{T}{d} \lfloor \frac{n}{T} \rfloor^2 \]

\[= \sum_{T=1}^n \phi(T) \lfloor \frac{n}{T} \rfloor^2 \]

每一步都是运用了 \(\mu\) 的基本性质，对最后一步的操作讲解一下：

你发现 \(\sum_{d|T} d \times \mu_{\frac{T}{d}}\) 这玩意儿很像 \(Id * \mu\)，然后就是了，而 \(Id * \mu = \phi\)，是不是很神奇？ 实际上是一个隐蔽的性质

推式子的基本要点总结：

1. 枚举 \(\gcd\) 并降枚举上限。

2. 用 \(\mu\) 套互质，然后瞬间和中间两个 \(\sum\) 说再见。

3. 再换元，更改循环顺序，用奇特的性质再消掉一个 \(\sum\)。

4. 观察模拟。

本题到了 \(\sum_{T=1}^n \phi(T) \lfloor \frac{n}{T} \rfloor^2\) 这步，直接枚举即可通过了。

时间复杂度：\(O(n)\). 实际得分：\(100pts\).

算法四

考虑推式子之后一个加强。

题意基本不变，改范围为：

\(T\) 组询问 \(n\) 的答案，\(T \leq 5 \times 10^5\)，\(n \leq 5 \times 10^5\).

显然 \(O(n \times T)\) 过不了。

考虑 \(\lfloor \frac{n}{T} \rfloor^2\) 可以整除分块，然后 \(\phi\) 可以预处理做前缀和。

这样可以单组询问 \(O(\sqrt{n})\)，预处理 \(O(n)\).

此处应当有掌声！

时间复杂度：\(O(n T \sqrt{n})\).

实际得分：\(100pts\).

#pragma GCC optimize(2)
#include<bits/stdc  .h>
using namespace std;

typedef long long ll;
const int N=1e5 1;

inline int read(){char ch=getchar(); int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3) (x<<1) ch-'0',ch=getchar();return x*f;}

ll s[N]; bool h[N];
int phi[N],prime[N],cnt=0;
int n; ll ans=0;

inline void Euler(int n) {
	phi[1]=1; s[1]=1;
	for(int i=2;i<=n;i  ) {
		if(!h[i]) phi[i]=i-1,prime[  cnt]=i;
		for(int j=1;j<=cnt && prime[j]*i<=n;j  ) {
			h[i*prime[j]]=1;
			if(i%prime[j]==0) {phi[i*prime[j]]=phi[i]*prime[j]; break;}
			phi[prime[j]*i]=phi[i]*(prime[j]-1);
		} s[i]=s[i-1] phi[i];
	}
} //预处理 phi 和 s (s 为前缀和)

int main() {
	Euler(N-1); n=read();
	for(int i=1;i<=n;) {
		ll t=n/(n/i);
		ans =1ll*(n/t)*(n/t)*(s[t]-s[i-1]);
		i=t 1; //整除分块板子
	} printf("%lld\n",ans);
	return 0;
}

附：本题没有取模，这是令人惊讶的一点——一般的大式子都要取模的。为什么呢？

因为，\(n=10^5\) 时答案才 \(72434344904\)，而答案总不会超过 \(n^3\) （每个 \(\gcd \leq n\) 哇，非常粗略的估算）。

\(n=10^6 \rightarrow ans = 8643257847824\).

\(n=10^7 \rightarrow ans = 1004297420038032\).

看到了吧，我们的估计大的多了，\(\text{long long}\) 没有问题的。

来源：https://www./content-4-686351.html