题解 P1447 【[NOI2010]能量采集】

· · 题解

纪念这道自己手推出来的数论题。

额，上古题解了，请大佬不要嘲讽，欧拉函数的卷积可以秒掉...

首先看到这道毒瘤题,我们可以先转化一下答案

不过好像有一点问题@communist 感谢大佬，已经修改

\text{answer} \iff 2\times\sum_{x=1}^n \sum_{y=1}^m (\gcd(x,y)-1) \iff 2\times\sum_{x=1}^n \sum_{y=1}^m (\gcd(x,y)) \ -n\times m

所以求出\sum_{x=1}^n \sum_{y=1}^m (\gcd(x,y))就好了

正好刚学过莫比乌斯反演，还有狄利克雷卷积，

然后我就开始暴力肝题了。

前置知识(\text{[POI2007]ZAP-Queries}) 先做这道题目

我的狄利克雷卷积总结不会的看这里

然后我们开始愉快的肝题:

先上套路:

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

设i=id,j=jd,就可以把d提出来了

f(d)=\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}[\gcd(i,j)==1] ∵[x==1]\Leftrightarrow \sum_{q|x}\mu(q) ∴f(d)=\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\sum_{q|i,q|j}\mu(q)

替换枚举q方式

∴f(d)=\sum_{i=1}^{\lfloor\frac nd}\sum_{j=1}^{\lfloor\frac md}\sum_{q=1}^{\lfloor\frac {\min(n,m)}d\rfloor}\mu(q)[q|i,q|j]

设i=iq,j=jq,就可以把\sum_{q=1}^{\lfloor\frac {\min(n,m)}d\rfloor}提出来了

∴f(d)=\sum_{q=1}^{\lfloor\frac {\min(n,m)}d\rfloor}\mu(q)\sum_{i=1}^{\lfloor\frac n{dq}\rfloor}\sum_{j=1}^{\lfloor\frac m{dq}\rfloor}1 f(d)=\sum_{q=1}^{\lfloor\frac {\min(n,m)}d\rfloor}\mu(q)\lfloor\frac n{dq}\rfloor\lfloor\frac m{dq}\rfloor

运用一下整除分块，暴力求出每一个f(k)\times k加起来就是\sum_{x=1}^n \sum_{y=1}^m \gcd(x,y)了。

时间复杂度O(\min(n,m)\sqrt {\min(n,m)})

结果只有90分，超时了。

我很绝望啊，结果重新推公式后，我发现有一步可以优化:

\sum_{x=1}^n \sum_{y=1}^m \gcd(x,y) =\sum_{d=1}^{\min(n,m)}f(d)\times d =\sum_{d=1}^{\min(n,m)}d\sum_{q=1}^{\frac {\min(n,m)}d}\mu(q)\lfloor\frac n{dq}\rfloor\lfloor\frac m{dq}\rfloor =\sum_{d=1}^{\min(n,m)}d\sum_{dq=1}^{\min(n,m)}\mu(q)\lfloor\frac n{dq}\rfloor\lfloor\frac m{dq}\rfloor

设T=dq

∴\ =\sum_{d=1}^{\min(n,m)}d\sum_{T=1}^{\min(n,m)}[d|T]\mu(\frac Td )\lfloor\frac n{T}\rfloor\lfloor\frac m{T}\rfloor =\sum_{d=1}^{\min(n,m)}\sum_{d|T}^{\min(n,m)}d\mu(\frac Td )\lfloor\frac n{T}\rfloor\lfloor\frac m{T}\rfloor

替换d,T枚举方式

=\sum_{T=1}^{\min(n,m)}\sum_{d|T}^{\min(n,m)}d\mu(\frac Td )\lfloor\frac n{T}\rfloor\lfloor\frac m{T}\rfloor =\sum_{T=1}^{\min(n,m)}\lfloor\frac n{T}\rfloor\lfloor\frac m{T}\rfloor\sum_{d|T}^{\min(n,m)}d\mu(\frac Td )

后面的东西有点眼熟。。。

这不是狄利克雷卷积吗?

设h(T)=\sum_{d|T}d\times\mu(\frac{T}{d}),写成卷积其实就是

h=id*\mu

然后两边都乘上函数1

h*1=id*(\mu*1) ∵\mu*1=ϵ ∴h*1=id*ϵ ∴h*1=id

我们又惊奇的发现

∵φ*1=id ∴h=φ 解了这么久再带入原式 $$\sum_{x=1}^n \sum_{y=1}^m \gcd(x,y)$$ $$=\sum_{T=1}^{\min(n,m)}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor \varphi(T)$$ 然后就很套路了。和$\text{ZAP Queries}$一样，预处理出欧拉函数前缀和，然后用整除分块，这个题目就$O(\min(n,m))$地解决了。 欧拉函数前缀和用欧拉筛求(什么鬼) ## 后记 信息数论和普通数论的区别就在于:它不一定是个结论题。你在推导的过程中，需要考虑——什么时候要停笔去枚举。 这也就是信息数论的难点所在。 ``` #include<bits/stdc++.h> using namespace std; int tot,T,vis[100004]; long long phi[100004],sum[100004],p[100004],n,m; inline void init(){//筛欧拉函数 int nx=100000;phi[1]=1; for (register int i=2;i<=nx;i++){ if (!vis[i]) p[++tot]=i,phi[i]=i-1; for (register int j=1;j<=tot&&i*p[j]<=nx;j++){ if (i*p[j]>nx) continue; vis[i*p[j]]=1; phi[i*p[j]]=phi[i]*phi[p[j]]; if((i%p[j])==0){ phi[i*p[j]]=phi[i]*p[j]; break; } } } for (int i=1;i<=nx;i++){ sum[i]=sum[i-1]+phi[i];//求前缀和 } } int main(){ scanf("%lld%lld",&n,&m); init(); long long ans=0; for (int l=1,r;l<=min(n,m);l=r+1){ r=min(n/(n/l),m/(m/l)); ans+=(long long)(sum[r]-sum[l-1])*(n/l)*(m/l);//整除分块 } ans=(long long)2*ans-n*m; printf("%lld",ans); } ```