Luogu

分析

这题好像咕了很久的样子...所以我就把过程写简单一点


杜教筛。

首先根据 $\varphi$ 的定义可以把原式化为 $\large\sum\limits_{i=1}^n\sum\limits_{j=1}^n\big(ij\sum\limits_{d|i,d|j}\varphi(d)\big)$ 。

反演得到 $\large\sum\limits_{d=1}^nd^2\varphi(d)sum(\lfloor\frac{n}{d}\rfloor)^2$ ,这里的 $sum(x)=\sum\limits_{i=1}^xi=\frac{x(x+1)}{2}$ 。

显然 $sum(\lfloor\frac{n}{d}\rfloor)^2$ 可以数论分块,那么考虑 $d^2\varphi(d)$ 的前缀和怎么求。

设 $f(d)=d^2\varphi(d)$ ,那么就是要求 $S(n)=\sum\limits_{i=1}^nf(i)$。

根据杜教筛那一套理论,有 $\large g(1)S(n)=\sum\limits_{i=1}^n(g*f)(i)-\sum\limits_{i=2}^ng(i)S(\lfloor\frac{n}{i}\rfloor)$ 。

考虑这个 $g$ 应该是什么。因为 $\sum\limits_{d|i}\varphi(d)=i$ ,所以我们可以让 $g(x)=x^2$ 。

那么 $\large(g*f)(i)=\sum\limits_{d|i}f(d)g(\frac{i}{d})=\sum\limits_{d|i}d^2\varphi(d)\frac{i^2}{d}=i^2\sum\limits_{d|i}\varphi(d)=i^3$ 。

最终有 $\large S(n)=\sum\limits_{i=1}^ni^3-\sum\limits_{i=2}^ni^2S(\lfloor\frac{n}{i}\rfloor)$ 。

根据小学奥数有 $\sum\limits_{i=1}^xi^3=\frac{x(x+1)(x+x+1)}{6}$ ,$\sum\limits_{i=1}^xi^2=\frac{x(x+1)}{2}$ ,都非常好计算。

那么直接杜教筛即可。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,mod,inv2,inv6;

inline int qpow(int a,int b) {
    int ans=1;
    for (;b;b>>=1,a=a*a%mod)
        if (b&1) ans=ans*a%mod;
    return ans;
}

inline int s_sqr(int x) { x%=mod; return 1ll*x*(x+1)%mod*inv2%mod; }
inline int s_cub(int x) { x%=mod; return 1ll*x*(x+1)%mod*(x+x+1)%mod*inv6%mod; }

const int N=8000000+10;

int p[N],v[N],cnt=0;
int phi[N],f[N];
unordered_map<int,int> M;

inline void sieve(int n) {
    phi[1]=v[1]=1;
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,phi[i]=i-1;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) phi[i*p[j]]=1ll*phi[i]*(p[j]-1)%mod;
            else { phi[i*p[j]]=1ll*phi[i]*p[j]%mod; break; }
        }
    }
    for (re int i=1;i<=n;++i) f[i]=(f[i-1]+phi[i]*i%mod*i%mod)%mod;
}

inline int sum(int x) {
    if (x<=8e6) return f[x];
    if (M.find(x)!=M.end()) return M[x];
    int ans=s_sqr(x)*s_sqr(x)%mod;
    for (re int i=2,j;i<=x;i=j+1) {
        j=x/(x/i);
        ans=(ans-sum(x/i)*(s_cub(j)-s_cub(i-1))%mod+mod)%mod;
    }
    return M[x]=ans;
}

signed main() {
    mod=read(),n=read(),inv2=qpow(2,mod-2),inv6=qpow(6,mod-2);
    sieve(8e6); int ans=0;
    for (re int i=1,j;i<=n;i=j+1) {
        j=n/(n/i);
        ans=(ans+(sum(j)-sum(i-1)+mod)%mod*s_sqr(n/i)%mod*s_sqr(n/i)%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 05 PM