51nod 1363 最小公倍数之和 ——欧拉函数

时间：2021-04-07 01:16:04
给出一个n，求1-n这n个数，同n的最小公倍数的和。
例如：n = 6，1,2,3,4,5,6 同6的最小公倍数分别为6,6,6,12,30,6，加在一起 = 66。
由于结果很大，输出Mod 1000000007的结果。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 50000)

第2 - T + 1行：T个数A[i](A[i] <= 10^9)
Output
共T行，输出对应的最小公倍数之和
Input示例
3

5

6

9
Output示例
55

66

279
————————————————————————
公式推导 51nod 1363 最小公倍数之和  ——欧拉函数
不过这里 最后枚举约数的时候 因为前面已经进行过质因数分解 所以可以直接枚举各个因数的次数就可以了
这样比直接枚举快很多（不会T QAQ
#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];

LL ly,yy;

int F(int x){for(int i=;i<=cnt;i++)if(x%p[i]==) x=x/p[i]*(p[i]-); return x;}

LL inv(int a,int b,LL&x,LL&y){

    if(!b){x=,y=;return a;}

    LL g=inv(b,a%b,y,x);

    y=(y-a/b*x)%mod;

    return g;

}

void dfs(int step,LL x){

    if(step==cnt+){

        if(x!=){

            inv(n/x,mod,ly,yy); ly=(ly+mod)%mod;

            ans=(ans+1LL*F(x)*n%mod*P%mod*ly%mod)%mod;

        }

        return ;

    }

    LL sum=;

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

        sum=(!i?:sum*p[step]);

        dfs(step+,x*sum);

    }

}

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=;

        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(,); printf("%lld\n",(n*ans+n)%mod);

    }

    return ;

}


 




相关文章