[51nod1190]最小公倍数之和V2（莫比乌斯反演）

ゝ一世哀愁。 2022-01-12 09:31 155阅读 0赞

## 题解 ##

[传送门][Link 1]

## 题解 ##

我是真的不明白这玩意儿是怎么跟反演扯上关系的……

首先

\\\[ \\begin\{align\} ans &=b\\sum\_\{d|b\}\{1\\over d\}\\sum\_\{i=a\}^\{b\}i\[\\gcd(i,b)=d\]\\\\ &=b\\sum\_\{d|b\}\\sum\_\{i=\\lceil\{a\\over d\}\\rceil\}^\{b\\over d\}i\[gcd(i,\{b\\over d\})=1\]\\\\ \\end\{align\} \\\]

然后有一个非常神仙的操作……就是强行反演一波，把\\(\[n=1\]\\)化成\\(\\sum\_\{i|n\}\\mu(i)\\)

\\\[ \\begin\{align\} ans &=b\\sum\_\{d|b\}\\sum\_\{i=\\lceil\{a\\over d\}\\rceil\}^\{b\\over d\}i\\sum\_\{j|\\gcd(i,\{b\\over d\})\}\\mu(j)\\\\ &=b\\sum\_\{d|b\}\\sum\_\{j|\{b\\over d\}\}\\mu(j)\\sum\_\{i=\\lceil\{a\\over d\}\\rceil\}^\{b\\over d\}\[i \\mod j=0\]\\\\ &=b\\sum\_\{d|b\}\\sum\_\{j|\{b\\over d\}\}\\mu(j)\\sum\_\{i=\\lceil\{a\\over d\}\\rceil\}^\{b\\over d\}\[i \\mod j=0\]\\\\ &=\{b\\over 2\}\\sum\_\{d|b\}\\sum\_\{j|\{b\\over d\}\}\\mu(j)j(\\lfloor\{b\\over \{dj\}\}\\rfloor+\\lceil\{a\\over \{dj\}\}\\rceil)(\\lfloor\{b\\over \{dj\}\}\\rfloor-\\lceil\{a\\over \{dj\}\}\\rceil+1)\\\\ &=\{b\\over 2\}\\sum\_\{T|b\}(\\lfloor\{b\\over T\}\\rfloor+\\lceil\{a\\over T\}\\rceil)(\\lfloor\{b\\over T\}\\rfloor-\\lceil\{a\\over T\}\\rceil+1)\\sum\_\{d|T\}\\mu(d)d\\\\ \\end\{align\} \\\]

那么我们只要把\\(b\\)分解一下质因数，然后\\(dfs\\)找出\\(b\\)的所有因子就可以了

然而这里还有一个问题，就是\\(f(T)=\\sum\_\{d|T\}\\mu(d)d\\)该怎么快速计算

首先我们可以发现\\(f\\)也是个积性函数，有\\(f(p)=1-p,f(p^c)=1-p\\)

因为只有次数小于等于\\(1\\)的质因子会有贡献，所以我们在爆搜枚举因数的时候，如果\\(p\\nmid i\\)，那么\\(f(i\\times p)=f(i)\\times(1-p)\\)

然后就没有然后了

//minamoto
    #include<bits/stdc++.h>
    #define R register
    #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
    #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
    #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
    using namespace std;
    char buf[1<<21],*p1=buf,*p2=buf;
    inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    int read(){
        R int res,f=1;R char ch;
        while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
        for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
        return res*f;
    }
    char sr[1<<21],z[20];int C=-1,Z=0;
    inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
    void print(R int x){
        if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
        while(z[++Z]=x%10+48,x/=10);
        while(sr[++C]=z[Z],--Z);sr[++C]='\n';
    }
    const int N=1e5+5,P=1e9+7,inv2=500000004;
    inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
    inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
    inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
    int ksm(R int x,R int y){
        R int res=1;
        for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);
        return res;
    }
    bitset<N>vis;int p[N],v[N],c[N],top,m,sqr,n,tot,res,g;
    void init(int n){
        fp(i,2,n){
            if(!vis[i])p[++tot]=i;
            for(R int j=1;j<=tot&&1ll*i*p[j]<=n;++j){
                vis[i*p[j]]=1;
                if(i%p[j]==0)break;
            }
        }
    }
    inline int calc(R int x,R int y){
        R int a=n/x,b=(m+x-1)/x;
        return 1ll*(a+b)*(a-b+1)%P*y%P;
    }
    void dfs(int pos,int val,int mu){
        if(pos==top+1)return res=add(res,calc(val,mu)),void();
        dfs(pos+1,val,mu),mu=mul(mu,dec(1,v[pos]));
        fp(i,1,c[pos])val*=v[pos],dfs(pos+1,val,mu);
    }
    void solve(){
        top=0,res=0,g=n;
        for(R int i=1;i<=tot&&1ll*p[i]*p[i]<=g;++i)if(g%p[i]==0){
            v[++top]=p[i],c[top]=0;
            while(g%p[i]==0)g/=p[i],++c[top];
        }
        if(g!=1)v[++top]=g,c[top]=1;
        dfs(1,1,1);
        res=1ll*res*n%P*inv2%P;
        print(res);
    }
    int main(){
    //  freopen("testdata.in","r",stdin);
    //  freopen("testdata.out","w",stdout);
        int T=read();init(sqr=N-5);
        while(T--)m=read(),n=read(),solve();
        return Ot(),0;
    }

转载于:https://www.cnblogs.com/bztMinamoto/p/10433146.html

[Link 1]: http://www.51nod.com/Challenge/Problem.html#!%23problemId=1190