[NOI2010]能量采集

显然题目要我们求

\(2\sum_{i=1}^N \sum_{j=1}^M (i,j) -NM\)

即

\(2\sum_{i=1}^{\min(N,M)} \phi(i)\lfloor \frac{N}{i} \rfloor \lfloor \frac{M}{i} \rfloor-NM\)

线筛+前缀和+整除分块即可

记得开\(long \ long\)

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=1e5+5;

int n,m;
long long ans;
int p[MAXN],phi[MAXN];
long long lis[MAXN];
bool b[MAXN];

int main()
{
    scanf("%d%d",&n,&m);if(n<m) swap(n,m);
    phi[1]=1;
    for(int i=2;i<=n;++i){
        if(!b[i]) p[++p[0]]=i,phi[i]=i-1;
        for(int j=1;j<=p[0]&&i*p[j]<=n;++j){
            b[i*p[j]]=1;
            if(i%p[j]) phi[i*p[j]]=phi[i]*phi[p[j]];
            else{phi[i*p[j]]=phi[i]*p[j];break;}
        }
    }for(int i=1;i<=n;++i) lis[i]=lis[i-1]+phi[i];
    for(int l=1,r;l<=m;l=r+1){
        r=min(n/(n/l),m/(m/l));
        ans+=(long long)(n/l)*(m/l)*(lis[r]-lis[l-1]);
    }ans=(ans<<1)-(long long)n*m;
    printf("%lld\n",ans);
    return 0;
}

[NOI2010]能量采集

原文：https://www.cnblogs.com/AH2002/p/10079671.html