P10670

Inui_Sana · 2024-09-01 10:03:42 · 题解

感觉我的做法更魔怔一点。

下取整显然不好搞。于是考虑套路化地变成 \sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{k=0}^{j-1}\frac{ik+x-(ik+x)\bmod j}{j}。\frac{ik+x}{j} 部分是好处理的，接下来就只考虑 \frac{(ik+x)\bmod j}{j}。

注意到 k 取遍 [0,j-1]，所以根据 \gcd(i,j) 相同的 i，\sum\limits_{k=0}^{j-1}\frac{(ik+x)\bmod j}{j} 是一样的，而这部分可以 O(1) 算。于是先枚举 j,\gcd(i,j) 再推式子。

然后套路莫反。

再把 d 往前提。

此时就可以枚举 l 再枚举 d 解决了，这个复杂度并没有什么很美丽的表达方式，但是可以写个程序算出计算次数大概是 5\times 10^7 的。稍微卡卡常，比如不用 vector，减少取模次数等，卡着时限过。

code：

int n,m,k,s,mu[N],pm[N],a[N][207],c[N];
bool vis[N];
il int Mod(int x,int y){
    return x+y>=mod?x+y-mod:x+y;
}
il int qpow(int x,int y){
    int ret=1;
    while(y){
        if(y&1){
            ret=1ll*ret*x%mod;
        }
        x=1ll*x*x%mod,y>>=1;
    }
    return ret;
}
void Yorushika(){
    read(n,m);
    double x;scanf("%lf",&x),k=x;
    rep(i,1,m){
        for(int j=i;j<=m;j+=i){
            a[j][++c[j]]=i;
        }
    }
    int ans=0;
    rep(j,1,m){
        int sum=0;
        sum=Mod(sum,1ll*((1ll*(1+n)*n/2)%mod)*((1ll*(j-1)*j/2)%mod)%mod);
        sum=Mod(sum,1ll*n*j%mod*k%mod);
        rep(i,1,c[j]){
            int l=a[j][i];
            ll x=0;
            rep(p,1,c[j/l]){
                int d=a[j/l][p];
                x+=1ll*mu[d]*(n/(d*l))*l;
            }
            int y=k%l;
            y=(1ll*(y+y+(j-l))*(j/l)/2)%mod;
            sum=Mod(sum,mod-1ll*(x%mod+mod)%mod*y%mod);
        }
        ans=Mod(ans,1ll*sum*qpow(j,mod-2)%mod);
    }
    printf("%d\n",ans);
}
signed main(){
    const int mx=5e5;
    mu[1]=1;
    rep(i,2,mx){
        if(!vis[i]){
            pm[++s]=i,mu[i]=-1;
        }
        rep(j,1,s){
            if(pm[j]>mx/i){
                break;
            }
            vis[i*pm[j]]=1;
            if(i%pm[j]==0){
                break;
            }
            mu[i*pm[j]]=-mu[i];
        }
    }
    int t=1;
    //read(t);
    while(t--){
        Yorushika();
    }
}