题解 P4466 【[国家集训队]和与积】

· · 题解

orz果然我反演还是幼儿园水平

让我们感受艾弗森记号的优越⑧!

\sum\limits_{i,j}[1\leq i<j\leq n][(i+j)\mid ij] =\sum\limits_{i,j,s,t,d}[1\leq i<j\leq n][d=\gcd(i,j)][i=sd][j=td][(i+j)\mid ij] =\sum\limits_{s,t,d}[1\leq sd<td\leq n][\gcd(s,t)=1][(s+t)d\mid std^2]

这里有必要处理一下最后面那个式子.首先我们知道它等价于[(s+t)\mid std]，然而事实上它还等价于(s+t)\mid d.

因为\gcd(s,t)=1，所以\gcd(s,s+t)=1,\gcd(s+t,t)=1，所以\gcd(s+t,st)=1，于是可以化成[(s+t)\mid d].继续化.

=\sum\limits_{s,t,d}[1\leq sd<td\leq n][\gcd(s,t)=1][(s+t)|d] =\sum\limits_{s,t,d,k}[d=k(s+t)][k\geq 1][\gcd(s,t)=1][1\leq sd<td\leq n] =\sum\limits_{s,t,k}[k\geq 1][\gcd(s,t)=1][1\leq ks(s+t)<kt(s+t)\leq n] =\sum\limits_{s,t,k}[k\in[1,\dfrac{n}{t(s+t)}]][s<t][\gcd(s,t)=1] =\sum\limits_{s,t}\left\lfloor\dfrac{n}{t(s+t)}\right\rfloor[\gcd(s,t)=1][s<t] =\sum\limits_{s,t,k}\left\lfloor\dfrac{n}{t(s+t)}\right\rfloor[k\mid s][k\mid t][s<t]\mu(k) =\sum\limits_{s,t,k}\left\lfloor\dfrac{n}{k^2t(s+t)}\right\rfloor[1\leq s<t]\mu(k)

注意到t>\sqrt{n}或k>\sqrt{n}时\left\lfloor\dfrac{n}{k^2t(s+t)}\right\rfloor=0，所以我们直接给它一个简单的上界并写成常见的形式

=\sum\limits_{k=1}^{\sqrt{n}}\mu(k)\sum\limits_{t=2}^{\sqrt{n}}\sum\limits_{s=1}^{t-1}\left\lfloor\dfrac{n}{k^2t(s+t)}\right\rfloor =\sum\limits_{k=1}^{\sqrt{n}}\mu(k)\sum\limits_{t=2}^{\frac{\sqrt{n}}{k}}\sum\limits_{s=t+1}^{2t-1}\left\lfloor\dfrac{n}{k^2st}\right\rfloor =\sum\limits_{k=1}^{\sqrt{n}}\mu(k)\sum\limits_{t=2}^\frac{\sqrt{n}}{k}\sum\limits_{s=t+1}^{2t-1}\left\lfloor\dfrac{\left\lfloor\frac{n}{k^2t}\right\rfloor}{s}\right\rfloor

这个式子...数论分块直接做...我也不知道复杂度具体是多少，只能口胡一波:

设S(n,t)=\sum\limits_{i=2}^n\sum\limits_{j=i+1}^{2i-1}\left\lfloor\frac{t}{is}\right\rfloor.

这东西暴力算的话是\sum\limits_{i=2}^nO(\sqrt{\frac{t}{i}})=O(\sqrt{nt})

原式=\sum\limits_{k=1}^{\sqrt{n}}\mu(k)S(\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor,\left\lfloor\frac{n}{k^2}\right\rfloor)的复杂度可以简单算成

\sum\limits_{k=1}^{\sqrt{n}}O(n^\frac{3}{4}k^{-\frac{3}{2}})=O(n^\frac{3}{4})

当然这太毒瘤了以至于我自己都不相信(((

rqy$说可以做到$O(n^\frac{2}{3})$反正我不会$QAQ

多组询问的话...太毒瘤了做不来QAQAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=5e5;
int mu[N],p[N],prime[N],n,sqt[N],cnt;
void make(int n)
{
    p[1]=mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!p[i])prime[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            int x=i*prime[j];p[x]=1;
            if(i%prime[j])mu[x]=-mu[i];
            else break;
        }
    }
    for(int i=2;i<=n;i++)mu[i]+=mu[i-1];
}
long long S(int l,int r,int n)
{
    r=min(n,r);long long ans=0;
    for(int i=l,lt;i<=r;i=lt+1)
    {
        lt=min(r,n/(n/i));
        ans+=1ll*(n/i)*(lt-i+1);
    }
    return ans;
}
long long calc(int n,int t)
{
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=S(i+1,2*i-1,t/i);
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    int sqn=sqrt(n);
    make(sqn);long long ans=0;
    for(int i=1;i<=sqn;i++)sqt[i]=sqrt(n/(n/(i*i)));
    for(int i=1,lt;i<=sqn;i=lt+1)
    {
        int f1=sqn/i,f2=n/(i*i);
        lt=min(sqn/f1,sqt[i]);
        ans+=(mu[lt]-mu[i-1])*calc(f1,f2);
    }
    printf("%lld\n",ans);
}