P1447 [NOI2010]能量采集
斯德哥尔摩
2018-08-02 10:08:22
[P1447 [NOI2010]能量采集](https://www.luogu.org/problemnew/show/P1447)
其实只要细心一点就会发现，题目要求：
$$Ans=\sum_{i=1}^n\sum_{j=1}^mf(gcd(i,j)),f(x)=2x-1$$
带入：$$Ans=\sum_{i=1}^n\sum_{j=1}^m(gcd(i,j)\times 2-1)$$
展开：$$Ans=2\times \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)-n\times m$$
于是就转化成了：
$$S=\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)$$
这玩意显然一发莫比乌斯反演啊：
$$S=\sum_{d|n}\sum_{i=1}^n\sum_{j=1}^md[gcd(i,j)==d]$$
即：
$$S=\sum_{d|n}d\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]$$
再把$d$换一下枚举方式：
$$S=\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]$$
前一个$\sum_{d=1}^nd$直接循环，后面那一堆$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]$就反演就好了。
莫比乌斯反演不会？看这题：[P3455 [POI2007]ZAP-Queries](https://www.luogu.org/blog/49998/p3455-poi2007zap-queries)
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
using namespace std;
int n,m;
int k=0,prime[MAXN],mu[MAXN],sum[MAXN];
bool np[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void make(){
int m=MAXN-10;
mu[1]=1;
for(int i=2;i<=m;i++){
if(!np[i]){
mu[i]=-1;
prime[++k]=i;
}
for(int j=1;j<=k&&prime[j]*i<=m;j++){
np[prime[j]*i]=true;
if(i%prime[j]==0)break;
else mu[prime[j]*i]=-mu[i];
}
}
for(int i=1;i<=m;i++)sum[i]=sum[i-1]+mu[i];
}
long long solve(long long n,long long m,long long d){
long long s=0;
n/=d;m/=d;
if(n>m)swap(n,m);
for(int i=1,last=1;i<=n;i=last+1){
last=min(n/(n/i),m/(m/i));
s+=(long long)(sum[last]-sum[i-1])*(n/i)*(m/i);
}
return s;
}
void work(){
long long ans=0;
for(int i=1;i<=n;i++)ans+=solve(n,m,i)*i;
printf("%lld\n",ans*2LL-1LL*n*m);
}
void init(){
n=read();m=read();
if(n>m)swap(n,m);
}
int main(){
make();
init();
work();
return 0;
}
```