给定n,m,k,计算
(sum_{i=1}^n sum_{j=1}^m mathrm{gcd}(i,j)^k)
对 (1000000007) 取模的结果
前置知识
式子还是正常的推
首先,(ID_k(x)=x^k)
[sum_{i=1}^{n} sum_{j=1}^{m} ID_k(gcd(i,j))
]
[sum_{d=1} ID_k(d)sum_{i=1}^{n} sum_{j=1}^{m} [gcd(i,j) =d]
]
[sum_{d=1} ID_k(d)sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor} [gcd(i,j) =1]
]
[sum_{d=1} ID_k(d)sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor} sum_{Dmid gcd(i,j)} mu(D)
]
[sum_{d=1} ID_k(d)sum_{D=1}^{min(n,m)}mu(D)sum_{i=1}^{lfloorfrac{n}{dD}
floor}sum_{j=1}^{lfloorfrac{m}{dD}
floor} 1
]
[sum_{d=1} ID_k(d)sum_{D=1}^{lfloor frac{n}{d}
floor}mu(D)lfloor frac{n}{dD}
floor lfloor frac{m}{dD}
floor
]
设 (T=dD)
[sum_{T=1}lfloor frac{n}{T}
floor lfloor frac{m}{T}
floor sum_{d|T} ID_k(d) mu(frac{T}{d})
]
我们发现后面这个东西就是狄利克雷卷积
我们管它叫 (f) 函数
也就是说
[f=ID_k*mu
]
由于积性函数卷积性函数还是积性函数
对于 (xin prime) (f(x)=x^k-1)
这样子就直接在线性筛的时候算一下就好了
代码:
void sieve(){
f[1]=1;
for(int i=2;i<MAXN;i++){
if(!vis[i]){
prime[++prime[0]]=i;
f[i]=(pw(i,k)-1+Mod)%Mod;
}
for(int j=1;j<=prime[0]&&i*prime[j]<MAXN;j++){
vis[i*prime[j]]=true;
if(i%prime[j]==0){f[i*prime[j]]=f[i]*(f[prime[j]]+1)%Mod;break;}
f[i*prime[j]]=f[i]*f[prime[j]]%Mod;
}
}
for(int i=1;i<MAXN;i++)s[i]=(s[i-1]+f[i])%Mod;
}