【题解】Luogu P1447 BZOJ P2005【能量采集】

背景

这道挂了三个多月的题现在终于AC了。

分析

很容易想到一个坐标为$(x,y)$植物连线上的植物数量就是$gcd(x,y)-1$,变一下柿子,就是求

\sum_{x=1}^{n}\sum_{y=1}^{m}\gcd(x,y)

然后$ans\div 2 – m \times n$
即求$gcd(i,j)$的幂,这很显然可以直接套反演,毕竟这就是反演推导柿子的应用。详情见这里

代码

#include<cstdio>
#include<algorithm>
using std::swap;using std::fill;
const int MAXN = 100000 + 6;
int pi[MAXN],mu[MAXN],num,sum[MAXN];
bool isPi[MAXN];
inline int min(int a,int b){return a < b ? a : b;}
void sieve(){
    fill(isPi,isPi + MAXN,true);
    mu[1] = 1,num = 0;
    for(int i = 2;i < MAXN;++i){
        if(isPi[i]) pi[num++] = i,mu[i] = -1;
        static int d;
        for(int j = 0;j < num && (d = i * pi[j]) < MAXN;++j){
            isPi[d] = false;
            if(i % pi[j] == 0){
                mu[d] = 0;break;
            }else mu[d] = -mu[i];
        }
    }
    sum[0] = 0;
    for(int i = 1;i < MAXN;i++) sum[i] = sum[i - 1] + mu[i];
}

long long f(int n,int m,int d){
    if(n > m) swap(n,m);
    n /= d,m /= d;
    long long ans = 0;
    for(int i = 1,last = 1;i <= n;i = last + 1){
        last = min(n / (n / i),m / (m / i));
        ans += (long long)(sum[last] - sum[i - 1]) * (long long)(n / i) * (long long)(m / i);
    }
    return ans;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    sieve();
    int n,m;long long ans = 0;scanf("%d %d",&n,&m);
    for(int d = 1;d <= n;d++) ans += (long long)d * f(n,m,d);
    printf("%lld",ans * 2 - (long long)m * n);

    return 0;
}

小结

写了线筛忘了调用,这个习惯不好,还打错了一次,要改。