zcmimi's blog
查看原题

点击跳转

带 套 路 题

\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\mu^2(\gcd(i,j))\gcd(i,j) \\ =\sum_{d=1}^n \mu^2(d) d \sum_{i=1}^n\sum_{j=1}^n(i+j)^k[\gcd(i,j)=d] \\ =\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor}(i+j)^k[\gcd(i,j)=1]

S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k

=\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor}(i+j)^k \sum_{x|i,x|j} \mu(x) \\ =\sum_{d=1}^n \sum_{x=1}^{\left \lfloor \frac nd \right \rfloor}\mu^2(d) d^{k+1} \mu(x) x^k S(\left \lfloor \frac n{dx} \right \rfloor)

T=dx

=\sum_{T=1}^n \sum_{d|T} \mu^2(d) d^{k+1} \mu(\frac Td) (\frac Td)^k S(\left \lfloor \frac nT \right \rfloor) \\ =\sum_{T=1}^n S(\left \lfloor \frac nT \right \rfloor) T^k \sum_{d|T} d \mu^2(d)\mu(\frac Td)

如何快速求令S(n)?

设:

F(n)=\sum_{i=1}^n i^k

G(n)=\sum_{i=1}^n F(i)

那么

S(n)=\sum_{i=n+1}^{2n}F(i)-\sum_{i=1}^nF(i) \\ =G(2n)-2G(n)

筛出F的前缀和,然后筛S(n)

优化:

因为模数是质数,根据欧拉定理: 对于互质的a,n满足a^{\varphi(n)} \equiv 1\pmod n

可以k=k \mod 998244352

求后半部分

f(n)=\sum_{d|n} d \mu^2(d)\mu(\frac nd)

如何线性求f(n)?

f(n)是若干个积性函数的卷积,所以f(n)也是积性函数

那么f(n)=f(p^k)f(\frac n{p^k})

f(1)=1

f(p^1)=p-1(带入即可得到)

f(p^2)=-p(带入即可得到)

f(p^k)=0(k\ge 3)

d\frac nd中必然有一个有平方因子,所以\mu(d)\mu(\frac nd)必有一项为0

所以f(p^k)=0(k\ge 3)

接下来就可以线性筛f(n)

#include<cstdio>
#define il inline
#define rg register
const int N=5000011,P=998244353;
int n,k,cnt=0,pri[5348514],F[N<<1],f[N];
bool b[N<<1];
il int pw(int x){
    int ans=1,b=k;
    while(b){
        if(b&1)ans=1ll*ans*x%P;
        b>>=1;x=1ll*x*x%P;
    }
    return ans;
}
il int M(int x){return x>=P?x-P:x;}
il int S(int n){return M(F[n<<1]-M(F[n]<<1)+P);}
int main(){
    long long _;
    scanf("%d%lld",&n,&_);k=_%(P-1);
    f[1]=F[1]=1;
    for(rg int i=2;i<=n;++i){
        if(!b[i])
            pri[++cnt]=i,
            f[i]=i-1,
            F[i]=pw(i);
        for(rg int j=1,x;j<=cnt&&(x=i*pri[j])<=n;++j){
            b[x]=1;
            F[x]=1ll*F[i]*F[pri[j]]%P;
            if(i%pri[j])f[x]=1ll*f[i]*f[pri[j]]%P;
            else{
                int t=i/pri[j];
                if(t%pri[j])f[x]=1ll*(P-pri[j])*f[t]%P;
                break;
            }
        }
    }
    for(rg int i=2;i<=n;++i)f[i]=M(f[i-1]+1ll*F[i]*f[i]%P);
    for(rg int i=n+1;i<=(n<<1);++i){
        if(!b[i])pri[++cnt]=i,F[i]=pw(i);
        for(rg int j=1,x;j<=cnt&&(x=i*pri[j])<=n;++j){
            b[x]=1;
            F[x]=1ll*F[i]*F[pri[j]]%P;
            if(!(i%pri[j]))break;
        }
    }
    for(rg int i=2;i<=(n<<1);++i)F[i]=M(F[i]+F[i-1]);
    for(rg int i=2;i<=(n<<1);++i)F[i]=M(F[i]+F[i-1]);
    int res=0;
    for(rg int l=1,r,i;l<=n;l=r+1){
        i=n/l,r=n/i;
        res=M(res+1ll*M(f[r]-f[l-1]+P)*S(i)%P);
    }
    printf("%d\n",res);
}
LG 6156 简单题
comment评论
Search
search