51NOD 1227：平均最小公倍数——题解

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1227

懒得打公式了，看这位的吧：https://blog.csdn.net/fromatp/article/details/74999989

又一次将我的智商下限刷低的一道题，论我根本没注意到[gcd(i,j)==1]*j=phi(i)*i/2这个悲催的事实。

果然我数学活该学不好。

#include<map>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int p=1e9+;

const int N=5e6;

const int M=2e6+;

const int MOD=;

const int INV2=;

const int INV6=;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int to,nxt,w;

}e[M];

bool he[N+];

int su[N+],tot,cnt,head[MOD+],phi[N+],sum[N+];

inline void add(int v,int w){

    int u=v%MOD;

    e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;

}

inline int query(int v){

    int u=v%MOD;

    for(int i=head[u];i;i=e[i].nxt)

        if(v==e[i].to)return e[i].w;

    return -;

}

inline int sub(int a,int b){

    a-=b;if(a<)a+=p;if(a>=p)a-=p;return a;

}

inline int inc(int a,int b){

    a+=b;if(a<)a+=p;if(a>=p)a-=p;return a;

}

inline int s1(int l,int r){

    return (ll)inc(l,r)*sub(r+,l)%p*INV2%p;

}

inline int s2(int n){

    return (ll)n*(n+)%p*(*n+)%p*INV6%p;

}

void Euler(int n){

    phi[]=;

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

        if(!he[i]){

            su[++tot]=i;phi[i]=i-;

        }

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

            int pri=su[j];he[i*pri]=;

            if(i%pri==){

                phi[i*pri]=phi[i]*pri;break;

            }else phi[i*pri]=phi[i]*phi[pri];

        }

    }

    for(int i=;i<=n;i++)sum[i]=inc(sum[i-],(ll)phi[i]*i%p);

}

int S(int n){

    if(n<=N)return sum[n];

    int tmp=query(n);

    if(tmp!=-)return tmp;

    int ans=;

    for(int i=,j;i<=n;i=j+){

        j=n/(n/i);

        ans=inc(ans,(ll)s1(i,j)*S(n/i)%p);

    }

    ans=sub(s2(n),ans);

    add(n,ans);

    return ans;

}

inline int f(int n){

    int ans=;

    for(int i=,j;i<=n;i=j+){

        j=n/(n/i);

        ans=inc(ans,(ll)S(n/i)*(j-i+)%p);

    }

    ans=(ll)(ans+n)*INV2%p;

    return ans;

}

int main(){

    Euler(N);

    int a=read(),b=read();

    printf("%d\n",sub(f(b),f(a-)));

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++