51nod 1190 最小公倍数之和 V2

给出2个数a, b，求LCM(a,b) + LCM(a+1,b) + .. + LCM(b,b)。

例如：a = 1, b = 6，1,2,3,4,5,6 同6的最小公倍数分别为6,6,6,12,30,6，加在一起 = 66。

由于结果可能很大，输出Mod 10^9 + 7的结果。（测试数据为随机数据，没有构造特别坑人的Test）

Input

第1行：一个数T，表示后面用作输入测试的数的数量。(1 <= T <= 50000)

第2 - T + 1行：每行2个数a, b，中间用空格分隔(1 <= a <= b <= 10^9)

Output

共T行，输出对应的最小公倍数之和Mod 10^9 + 7的结果。

Input示例

Output示例

66

675

139860
—————————————————————————————————
这道题可以转化一下公式变成莫比乌斯反演 

d*mu(d) 因为是积性函数 所以可以直接推 这样就完成辣2333

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

const int M=1e5+,mod=1e9+,P=(mod+)/,mx=4e4+;

using std::max;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int T,n,p[M],cnt,h[M],pri[mx],xp;

LL v,ans,vis[mx],l;

void dfs(int step,LL T,LL g){

    if(step==cnt+){

        ans=(ans+((+n/T)*(n/T)/-(+l/T)*(l/T)/)%mod*g%mod)%mod;

        return ;

    }

    LL sum=;

    dfs(step+,T*sum,g);

    for(int i=;i<=h[step];i++){

        sum=sum*p[step];

        dfs(step+,T*sum,g*(-p[step]));

    }

}

int main(){

    T=read();

    for(int i=;i<=mx;i++)if(!vis[i]){

        pri[++xp]=i; vis[i]=;

        for(int j=*i;j<=mx;j+=i) vis[j]=;

    }

    while(T--){

        cnt=; ans=;

        l=read()-; n=read(); v=n;

        for(LL x=;pri[x]*pri[x]<=v;x++)if(v%pri[x]==){

            p[++cnt]=pri[x]; h[cnt]=;

            while(v%pri[x]==) v/=pri[x],h[cnt]++;

        }

        if(v!=) p[++cnt]=v,h[cnt]=;

        dfs(,,); ans=(ans%mod+mod)%mod;

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

    }

    return ;

}

巴特西

51nod 1190 最小公倍数之和 V2

最新文章

热门文章