题解 | #简单的数学题#

B题：简单的数学题
大概思路是杜教筛+莫比乌斯反演+枚举+整除分块优化+记忆化优化

代码如下：

#include<iostream>
#include<string.h>
#include<unordered_map>

#define lint long long

#define mod 1000000007

#define pren 5000007
#define dnprime 5000007

using
        namespace
                    std;

bool isprime[pren];
lint prime[dnprime],nprime;
lint myu[pren],smyu[pren];

unordered_map<lint,lint> bsmyu;
unordered_map<lint,lint> preans,subpreans;

void prework(){
    memset(isprime,true,sizeof(isprime));
    memset(myu,0,sizeof(myu));
    nprime=0;
    myu[0]=0,myu[1]=1;

    for(lint i=2;i<pren;i++){
        if(isprime[i]){
            prime[nprime]=i;
            myu[i]=-1;
            nprime++;
        }
        for(lint j=0;j<nprime&&i*prime[j]<pren;j++){
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0){
                myu[i*prime[j]]=0;
                break;
            }
            else{
                myu[i*prime[j]]=-myu[i];
            }
        }
    }

    smyu[0]=0;
    for(int i=1;i<pren;i++){
        smyu[i]=smyu[i-1]+myu[i];
    }

    return;
}

lint find_smyu(lint x){
    if(x<pren) return smyu[x];
    if(bsmyu[x]) return bsmyu[x];
    lint ans=1;
    for(lint l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans-=(r-l+1)*(find_smyu(x/l));
    }
    return bsmyu[x]=ans;
}

lint subcal(lint x){
    if(subpreans[x]) return subpreans[x];
    lint ans=x;
    for(lint l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans=(        ans
                +
                    (
                        ((r+l)*(r-l+1)/2)%mod
                        *
                        ((1+x/l)*(x/l)/2)%mod
                    )%mod
                +
                    (
                        (x*l)%mod
                        *
                        (x/(l-1)-x/l)
                    )%mod
                -
                    (
                        ((l*(l-1))/2)%mod
                        *
                        ((x/(l-1)-x/l)*(x/(l-1)+x/l+1))%mod

                    )%mod
            )%mod;
    }
    if(ans<0) ans+=mod;
    return subpreans[x]=ans;
}

lint cal(lint x){
    if(preans[x]) return preans[x];
    lint ans=0;
    for(lint l=1,r;l<=x;l=r+1){
        r=x/(x/l);
        ans=(ans+(find_smyu(r)-find_smyu(l-1))*(subcal(x/l)))%mod;
    }
    if(ans<0) ans+=mod;
    return preans[x]=ans;
}

signed main(){
    prework();
    int t;
    lint x;
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&x);
        printf("%lld\n",cal(x));
    }
    return EOF+1;
}