bzoj 4804 欧拉心算 题解

题意简述

T组数据。每次给定n，求$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\phi(gcd(i,j))$
n<=10^7，T<=5000。 （用T根号n的算法就能过了）

思路框架

把gcd换掉，然后用[SDOI2008]仪仗队（洛谷 bzoj）的做法，每次根号(n)求出来

具体思路

把$gcd$换掉，式子变成
$\sum\limits_{g=1}^n\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} [gcd(i,j)==g] \phi(g)$
$\phi(g)$提前，变成
$\sum\limits_{g=1}^n \phi(g) \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} [gcd(i,j)==g]$
后面那个式子化一下，变成枚举$i,j$的倍数：
$\sum\limits_{g=1}^n \phi(g) \sum\limits_{i=1}^{n/g}\sum\limits_{j=1}^{n/g} [gcd(i,j)==1]$

然后，后面的式子就变成了仪仗队那题的式子了。也就是，我们要求：
$\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{x} [gcd(i,j)==1]$。由于前面$g$要整除分块，带一个根号，所以这个地方就要用一个$O(1)$的算法求。

仪仗队那题的O(1)做法

由于$gcd(i,j)$是对称的，所以我们考虑把它变成这样：
$2\times \sum\limits_{i=1}^{x}\sum\limits_{j=1}^{i} [gcd(i,j)==1]-\sum\limits_{i=1}^{x} [gcd(i,i)==1]$。
我们设$\phi’(i)=\phi(1…i)$的和。（即：求$\phi$的前缀和）
那么该式等于$2\phi’(i)-1$。

得解

回到原问题。上回说到，式子变成了$\sum\limits_{g=1}^n \phi(g) \sum\limits_{i=1}^{n/g}\sum\limits_{j=1}^{n/g} [gcd(i,j)==1]$。
套用仪仗队那题的式子，变成：
$\sum\limits_{g=1}^{n} \phi(g)\times(2\phi’(n/g)-1)$

后面的$n/g$珂以整除分块做。总体复杂度就是$O(1e7+T\times\sqrt{n})=O(AC)$。

WARNING

只有phi的前缀和以及答案需要开long long ，其它int就够了。防止MLE。

代码

复制

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 10000007
    #define lovelive long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt)
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
 
    int primes[N];bool notp[N];
    int phi[N];lovelive sphi[N]; //处理phi的前缀和，记得开long long 
    void Init() //筛
    {
        int &cnt=primes[0];
        int n=1e7;
        notp[1]=1;phi[1]=1;
        F(i,2,n)
        {
            if (!notp[i]) primes[++cnt]=i,phi[i]=i-1;
            for(int j=1;j<=cnt and i*primes[j]<=n;++j)
            {int u=primes[j];
                notp[i*u]=1;
                if (i%u==0)
                {
                    phi[i*u]=phi[i]*u;break;
                }
                else
                {
                    phi[i*u]=phi[i]*phi[u];
                }
            }
        }
        F(i,1,n) sphi[i]=sphi[i-1]+phi[i]; 
        //以上O(n)
    }
    int n;
    void Input()
    {
        R1(n);
    }
    void Soviet()
    {
        lovelive ans=0;
        for(int l=1,r;l<=n;l=r+1)
        {r=n/(n/l);
            ans+=(sphi[r]-sphi[l-1])*(2ll*sphi[n/l]-1ll); //整除分块
        }
        printf("%lld\n",ans);
    }
 
    #define Flan void
    Flan IsMyWife()
    {
        Init();
        int t;R1(t);
        F(i,1,t)
        {
            Input();
            Soviet();
        }
    }
    #undef int //long long
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}