题目

求$\sum\limits_{i = 1} ^ n 2f_2(i)+3f_1(i)+5f_0(i)$ 对 998244353 取模，其中$f_k(i)=\sum_{d|i} d^k$，$n \le {10} ^ 9$。

题解

以 $f_2(i)$ 为例，当 $n=10$ 有：
$f_2(1)=1^2$
$f_2(2)=1^2+2^2$
$f_2(3)=1^2+3^2$
$f_2(4)=1^2+2^2+4^2$
$f_2(5)=1^2+5^2$
$f_2(6)=1^2+2^2+3^2$
$f_2(7)=1^2+7^2$
$f_2(8)=1^2+4^2+8^2$
$f_2(9)=1^2+3^2+9^2$
$f_2(10)=1^2+5^2+10^2$
设 $F_2(n)=f_2(1)+f_2(2)+f_2(3)+ \dots +f_2(n)$
研究：$i^2$ 在 $F_2(n)$中出现了多少次？
例如：$3^2$ 在 $F_2(10)$中出现了多少次？
$3^2$ 在 $f_2(3)、f_2(6)、f_2(9)$ 中出现，即是在 $F_2(10)$ 中出现了3次，即出现了 $\lfloor \frac{10}{3} \rfloor$ 次。
所以可知：$i^2$ 在 $f_2(i)、f_2(2i)、f_2(3i) \dots f_2(\lfloor \frac{n}{i} \rfloor*i )$ 中出现，即是在 $F_2(n)$ 中出现了 $\lfloor \frac{n}{i} \rfloor$ 次。
由此可得： $F_2(n)=\sum\limits_{i=1}^ni^2*\lfloor\frac{n}{i}\rfloor$
同理： $F_0(n)=\sum\limits_{i=1}^n1*\lfloor\frac{n}{i}\rfloor$ , $F_1(n)=\sum\limits_{i=1}^ni*\lfloor\frac{n}{i}\rfloor$ 。

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr LL N=1e7+10,mod=998244353;
LL F0,F1,F2,inv6;
inline LL qpow(LL a,LL b)
{
    LL res=1;
    for(;b;b>>=1,a=1ll*a*a%mod)if(b&1) res=1ll*res*a%mod;
    return res;
}
LL calc(int n)
{
    return 1ll*n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}
int main()
{
    int n;scanf("%d",&n);
    inv6=qpow(6,mod-2);
    LL ans=F0=F1=F2=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        F2=(F2+ 1ll*(calc(r)-calc(l-1)+mod)%mod*(n/l)%mod)%mod;
        F1=(F1+ 1ll*(r+l)*(r-l+1)/2 %mod*(n/l)%mod)%mod;
        F0=(F0+ 1ll*(r-l+1)*(n/l)%mod)%mod;
    }
    ans=(2*F2+3*F1+5*F0)%mod;
    printf("%lld\n",ans);
    return 0;
}