【BZOJ4804】欧拉心算(欧拉函数)

点此看题面

大致题意: 求\(\sum_{i=1}^n\sum_{j=1}^n\phi(gcd(i,j))\)。

前言

\(Jan\ 28th\)刷题计划(1/6),算法标签:莫比乌斯反演&杜教筛(强烈投诉,思路直接被这个算法标签带歪了,其实根本用不到莫比乌斯反演啊......)。

这道题其实是很套路的,和【CCPC-Wannafly Winter Camp Day3 (Div1) F】小清新数论这道题很像,而且由于数据范围还能省去杜教筛。

欧拉函数

强调:这道题完全不需要用到\(\mu\)!

考虑按照做这种题的经典套路,我们枚举\(gcd\),得到:

\[\sum_{d=1}^n\phi(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}[gcd(i,j)==1]\]

看到后面这个\([gcd(i,j)==1]\)的式子,是不是立马有一种反演的冲动?

然而,如果此时你选择了反演,最终将得到一个很麻烦的式子,因此我们采取另一种做法。

现单独考虑\(\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}[gcd(i,j)==1]\)这个式子。

如果\(i<j\),那么交换\(i,j\),就唯一对应一种\(i>j\)的情况。

如果\(i=j\),那么当且仅当\(i=j=1\)时,\(gcd(i,j)=1\)。

所以我们把它转化成只考虑\(i\ge j\)的情况,这个式子就等同于:

\[\sum_{i=1}^{\lfloor\frac nd\rfloor}(2\sum_{j=1}^{i}[gcd(i,j)==1]-1)\]

其中之所以要减\(1\),是因为\(i=j=1\)的情况被重复算了两遍。

然后我们发现式子中的\(\sum_{j=1}^{i}[gcd(i,j)==1]\)就相当于是\(\phi(i)\)(这就是欧拉函数的定义)。

所以,原式就被化简为:

\[\sum_{d=1}^n\phi(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}(2\phi(i)-1)\]

于是我们对\(\phi\)做一个前缀和,接下来就是很套路的除法分块了。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 10000000
using namespace std;
int n;
template<int SZ> class LinearSieve//线性筛
{
    private:
        int Pt,P[SZ+5],phi[SZ+5];long long s[SZ+5];
    public:
        I long long operator [] (CI x) Con {return s[x];}
        I LinearSieve()
        {
            RI i,j;for(phi[1]=s[1]=1,i=2;i<=SZ;++i)
            {
                !P[i]&&(phi[P[++Pt]=i]=i-1),s[i]=s[i-1]+phi[i];
                for(j=1;j<=Pt&&i*P[j]<=SZ;++j)
                    if(P[i*P[j]]=1,i%P[j]) phi[i*P[j]]=phi[i]*(P[j]-1);
                    else {phi[i*P[j]]=phi[i]*P[j];break;}
            }
        }
};LinearSieve<N> Phi;
int main()
{
    RI Tt,l,r;long long t;scanf("%d",&Tt);W(Tt--)
    {
        for(scanf("%d",&n),t=0,l=1;l<=n;l=r+1)//除法分块
            r=n/(n/l),t+=(Phi[r]-Phi[l-1])*(2*Phi[n/l]-1);
        printf("%lld\n",t);
    }return 0;
}
上一篇:刚性方程


下一篇:【BZOJ 3512】 DZY Loves Math IV(杜教筛+记忆化搜索)