BZOJ2005: [Noi2010]能量采集

题目描述

传送门

题目分析

可以直接通过一些推算发现题目实际上就是在求：

[Ans=2 imes sum_{i=1}^{n}sum_{j=1}^{m}(gcd(i,j)-1 ) ]

把里面的(1)提出来，式子变成：

[Ans=2 imessum_{i=1}^{n}sum_{j=1}^{m}gcd(i,j)-2 imes nm ]

可以发现前面那个式子好像很熟悉，我们设：

[S(n)=sum_{i=1}^{n}sum_{j=1}^{m}gcd(i,j) ]

那么我们把这个式子化出来就可以了。

[egin{aligned} S(n)&=sum_{i=1}^{n}sum_{j=1}^{m}gcd(i,j)\ &=sum_{d=1}^{min(n,m)}sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=d]d\ &=sum_{d=1}^{min(n,m)}dsum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=d]\ &=sum_{d=1}^{min(n,m)}dsum_{dmid x}mu(frac{x}{d})lfloorfrac{n}{x} floorlfloorfrac{m}{x} floor\ &=sum_{d=1}^{min(n,m)}dsum_{T=1}^{min(frac{n}{d},frac{m}{d})}mu(T)lfloorfrac{n}{dT} floorlfloorfrac{m}{dT} floor\ &=sum_{d=1}^{min(n,m)}sum_{dmid T}^{min(n,m)}dmu(frac{T}{d})lfloorfrac{n}{T} floorlfloorfrac{m}{T} floor\ &=sum_{T=1}^{min(n,m)}lfloorfrac{n}{T} floorlfloorfrac{m}{T} floorsum_{dmid T}^{min(n,m)}mu(frac{T}{d})\ &=sum_{T=1}^{min(n,m)}lfloorfrac{n}{T} floorlfloorfrac{m}{T} floorvarphi(T) end{aligned} ]

化到这个地方就差不多了，这个式子明显是可以整除分块做的。但是，这个题数据支持线性做法。。。
直接做就行。

是代码呢

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+7;
#define ll long long
int prime[MAXN],n,m;
ll phi[MAXN],sum;
bool vis[MAXN];
inline void get_phi(int N)
{
    phi[1]=1;
    for(int i=2;i<=N;i++){
        if(!vis[i]){
            prime[++prime[0]]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=prime[0];j++){
            if(i*prime[j]>N) break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            } else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int main()
{
    cin>>n>>m;
    sum=-1ll*n*m;
    get_phi(1000000);
    for(int i=1;i<=min(n,m);i++) sum+=1ll*2*(n/i)*(m/i)*phi[i];
    printf("%lld
", sum);
}