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

· · 个人记录

求

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

非常水，我们直接上套路

f(n)=\sum_{i=1}^N\sum_{j=1}^M[(i,j)=n] F(n)=\sum_{n|d}f(d)=\left \lfloor \frac{N}{n} \right \rfloor\times\left \lfloor \frac{M}{n}\right \rfloor

直接反演

f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)

我们的答案就是

Ans=\sum_{i=1}^Ni\times f(i)=\sum_{i=1}^Ni\times\sum_{i|d}\mu(\frac{d}{i})F(d) =\sum_{i=1}^Ni\times\sum_{i|d}\mu(\frac{d}{i})\times\left \lfloor \frac{N}{d} \right \rfloor\times\left \lfloor \frac{M}{d}\right \rfloor

我们把d放到外面去枚举

那么

Ans=\sum_{d=1}^N\left \lfloor \frac{N}{d} \right \rfloor\times\left \lfloor \frac{M}{d}\right \rfloor\sum_{i|d}\mu(\frac{d}{i})\times i

之后惊奇的发现后面实际上就是\mu\times id

所以后面其实就是\varphi

所以现在答案是

Ans=\sum_{d=1}^N\left \lfloor \frac{N}{d} \right \rfloor\times\left \lfloor \frac{M}{d}\right \rfloor\times \varphi(d)

整除分块可以做到O(N+T\sqrt{N})

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define maxn 100005
#define LL long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
        x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
int f[maxn],phi[maxn],p[maxn];
int n,m;
int main()
{
    n=read(),m=read();
    if(n>m) std::swap(n,m);
    f[1]=1,phi[1]=1;
    for(re int i=2;i<=n;i++)
    {
        if(!f[i]) p[++p[0]]=i,phi[i]=i-1;
        for(re int j=1;j<=p[0]&&p[j]*i<=n;j++)
        {
            f[p[j]*i]=1;
            if(i%p[j]==0)
            {
                phi[p[j]*i]=phi[i]*p[j];
                break;
            }
            phi[p[j]*i]=(p[j]-1)*phi[i];
        }
    }
    for(re int i=1;i<=n;i++) phi[i]+=phi[i-1];
    LL ans=0;
    for(re int l=1,r;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans+=(LL)(n/l)*(m/l)*(phi[r]-phi[l-1]);
    }
    std::cout<<2ll*ans-(LL)n*(LL)m;
    return 0;
}