P1447 [NOI2010]能量采集

· · 个人记录

P1447 [NOI2010]能量采集

其实只要细心一点就会发现，题目要求：

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

附代码：

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