[HDU - 6833] A Very Easy Math Problem (莫比乌斯反演)

Posted on Edited on In

[HDU - 6833] A Very Easy Math Problem (莫比乌斯反演)

与 \(\gcd\) 有关的问题，很容易想到莫比乌斯反演

设 \(G(a,n)=(\sum_{i=1}^{\lfloor \frac{n}{a} \rfloor } (ai)^k)^x\)

\(Ans=\sum_{g=1}^{n} g\cdot f(g)\cdot \sum _{d=1}^{\lfloor\frac{n}{g}\rfloor} \mu(d) G(gd,n)\)

对于单组询问，显然可以 \(O(n\ln n)\) 求解

考虑优化

可以在 \(O(n\ln n)\) 的时间内，对于每个 \(i\) ，求出 \(F(i)=\sum_{d|i}\mu(d)\cdot \frac{i}{d} f(\frac{i}{d})\)

对于 \(G(a,n)\) 的求解，参数分离后发现 \(G(a,n)=a^{kx}(\sum_{i=1}^{\lfloor \frac{n}{a} \rfloor } i^k)^x\)

可以预处理出 \(S(n)=\sum_{i=1}^n i^{kx}\cdot F(i)\) 前缀和以及 \(A(n)=(\sum_{i=1}^{n}i^k)^x\) ，对于每个 \(\lfloor \frac{n}{a}\rfloor\) 考虑即可

数论分段的复杂度为单组查询 \(O(\sqrt n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=2e5+10,P=1e9+7;

int T,n,k,x;
int mk[N],notpri[N],pri[N],pc,w[N];
ll qpow(ll x,ll k=P-2) {
    ll res=1;
    for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
    return res;
}
int s[N],F[N],S[N],A[N];


int main(){
    w[1]=1;
    rep(i,2,N-1) {
        if(!notpri[i]) pri[++pc]=i,w[i]=-1;
        for(int j=1;j<=pc && 1ll*i*pri[j]<N;++j) {
            notpri[i*pri[j]]=1;
            if(i%pri[j]==0) {
                w[i*pri[j]]=0;
                break;
            }
            w[i*pri[j]]=-w[i];
        }
    }
    for(int i=2;i*i<N;++i) for(int j=i*i;j<N;j+=i*i) mk[j]=1;
    rep(i,1,N-1) if(!mk[i]) rep(j,1,(N-1)/i) F[i*j]=(F[i*j]+i*w[j]+P)%P;
    T=rd(),k=rd(),x=rd();
    rep(i,1,N-1) S[i]=(S[i-1]+F[i]*qpow(i,1ll*k*x))%P;
    rep(i,1,N-1) A[i]=(A[i-1]+qpow(i,k))%P;
    rep(i,1,N-1) A[i]=qpow(A[i],x);
    rep(kase,1,T) {
        n=rd();
        ll ans=0;
        for(int i=1,j;i<=n;i=j+1) {
            j=n/(n/i);
            ans=(ans+1ll*(S[j]-S[i-1])*A[n/i])%P;
        }
        ans=(ans%P+P)%P;
        printf("%lld\n",ans);
    }
}