【Luogu】P3327约数个数和（莫比乌斯反演+神奇数论公式）

　　题目链接

　　真TM是神奇数论公式。

　　注明：如无特殊说明我们的除法都是整数除法，向下取整的那种。

　　首先有个定理叫$d(ij)=\sum\limits_{i|n}{}\sum\limits_{j|m}{}(gcd(i,j)==1)$

　　证明……我不会证qwq，可以看这个链接

　　所以原式$\sum\limits_{i=1}{n}\sum\limits_{j=1}{m}d(ij)$

　　　　　　=$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{k=1}^{i}\sum\limits_{l=1}^{j}[gcd(k,l)==1]$

　　　　　　=$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{n}{i}\frac{m}{j}[gcd(i,j)==1]$

　　等等这个等号是怎么推过来的？题解一笔带过，然而我死活没看懂，于是请教rqy……

　　以下是rqy的解析。

　　$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{k=1}^{i}\sum\limits_{l=1}^{j}[gcd(k,l)==1]$

　　=$\sum\limits_{a=1}^{n}\sum\limits_{b=1}^{m}[gcd(a,b)==1]\sum\limits_{a|i}^{1<=i<=n} \sum\limits_{b|j}^{1<=j<=m}1$

　　=$\sum\limits_{a=1}^{n}\sum\limits_{b=1}^{m}[gcd(a,b)==1]\frac{n}{a}\frac{m}{b}$

　　然后把a统统替换成i，把b统统替换成j

　　就证明完毕啦

　　然后我们有了这个东西有什么用呢？

　　emm公式打不出来了……看Night_Aurora的题解……

设

那么可发现

所以下文对于FS函数若第三项省略则表示第三项为1

根据莫比乌斯反演

那么

那么答案就是F(N,M)了

最后只差O(1)处理S函数了

我们再设

我们发现S(n,m)=V(n)*V(m)

那么我们只要开始用O(N)打一个μ的前缀和

再用O(N^1.5)试除法求出前50000个V函数的表

再对每组询问进行试除法

总复杂度是

　　贴上我的代码

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<cstdlib>

#define maxn 50060

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

bool s[maxn];

int prime[maxn],tot;

int miu[maxn];

long long v[maxn];

int main(){

    miu[]=;

    for(int i=;i<=maxn;++i){

        if(!s[i]){

            prime[++tot]=i;

            miu[i]=-;

        }

        for(int j=;j<=tot&&prime[j]*i<=maxn;++j){

            s[i*prime[j]]=;

            if(!(i%prime[j]))    break;

            miu[i*prime[j]]=-miu[i];

        }

    }

    for(int i=;i<=maxn;++i)    miu[i]+=miu[i-];

    for(int n=;n<=maxn;++n){

        int x=;

        while(x<=n){

            int y=n/(n/x);

            v[n]+=(y-x+)*(n/x);

            x=y+;

        }

    }

    int T=read();

    while(T--){

        int n=read(),m=read();    long long ans=;

        int x=,top=min(n,m);

        while(x<=top){

            int y=min(n/(n/x),m/(m/x));

            ans+=(long long)(v[n/y]*(long long)v[m/y])*(long long)(miu[y]-miu[x-]);

            x=y+;

        }

        printf("%lld\n",ans);

    }

    return ;

}

　　这篇博客……勉勉强强算是写（抄）完了吧……

巴特西

【Luogu】P3327约数个数和（莫比乌斯反演+神奇数论公式）

最新文章

热门文章