P6156 题解
Sharing666
·
·
个人记录
莫比乌斯反演。推柿子。
\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^k f(\gcd(i,j)) \gcd(i,j)
\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^k\sum\limits_{d=1}^n\left[\gcd(i,j)=d\right]f(d) d
\sum\limits_{d=1}^n f(d)d\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left[\gcd(i,j)=1\right](id+jd)^k
\sum\limits_{d=1}^n f(d)d^{k+1}\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left[\gcd(i,j)=1\right](i+j)^k
\sum\limits_{d=1}^n f(d)d^{k+1}\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{l=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left[l|d\right]\mu(l)(i+j)^k
\sum\limits_{d=1}^n f(d)d^{k+1}\sum\limits_{l=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(l)\sum\limits_{i=1}^{\left\lfloor\frac{n}{dl}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{n}{dl}\right\rfloor}(il+jl)^k
\sum\limits_{d=1}^n f(d)d^{k+1}\sum\limits_{l=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(l)l^k\sum\limits_{i=1}^{\left\lfloor\frac{n}{dl}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{n}{dl}\right\rfloor}(i+j)^k
前面的部分可以分块 O(n \sqrt n) 处理，关键是怎么预处理后面的部分。不难发现：
\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}(i+j)^k=\sum\limits_{i=1}^{m}(i+1)^k+(i+2)^k+\dots+(i+n)^k=1(1+1)^k+2(1+2)^k+\cdots+(n-1)n^k+n(n+1)^k+(n-1)(n+2)^k+\dots+2(2n-1)^k+1(2n)^k
这个东西可以通过线性筛筛 1 到 2n 每个数的 k 次幂，求两次前缀和得出。
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
#define mod 998244353
int n,p[5000002],mu[5000002];
long long k,pow[10000002],sum[10000002],res[5000002];
bool vis[10000002];
long long power(long long x,long long y) {
long long tot=1;
while(y) {
if(y%2) tot=(tot*x)%mod;
x=(x*x)%mod,y/=2;
}
return tot;
}
void getmu() {
vis[1]=pow[1]=mu[1]=sum[1]=1;
for(int i=2;i<=10000000;i++) {
if(!vis[i]) {
p[++p[0]]=i,pow[i]=power(i,k);
if(i<=5000000) mu[i]=-1;
}
for(int j=1;i*p[j]<=10000000;j++) {
vis[i*p[j]]=1;
pow[i*p[j]]=(pow[i]*pow[p[j]])%mod;
if(i%p[j]==0) break;
if(i*p[j]<=5000000) mu[i*p[j]]=-mu[i];
}
sum[i]=(sum[i-1]+pow[i])%mod;
}
for(int i=1;i<=10000000;i++) {
if(i<=5000000) res[i]=(res[i-1]+pow[i]*mu[i])%mod;
sum[i]=(sum[i-1]+sum[i])%mod;
}
}
int main() {
scanf("%d%lld",&n,&k);
getmu();
long long ans=0;
for(int i=1;i<=n;i++) {
int l=1,r=1;
long long tot=0;
while(l<=n/i) {
r=(n/i)/((n/i)/l);
tot=(tot+(res[r]-res[l-1])%mod*(sum[2*(n/i/l)]-2*sum[n/i/l])%mod)%mod;
l=r+1;
}
ans=(ans+((i*pow[i])%mod*mu[i]*mu[i]*tot)%mod)%mod;
}
printf("%lld\n",(ans%mod+mod)%mod);
return 0;
}
```
（我一开始没看 $k$ 的数据范围用了 $int$ 然后一直wa，还以为柿子推错了/kk）