正題

題目鏈接:https://www.luogu.com.cn/problem/P4449

---

題目大意

$T$組詢問給出$n,m$求$$\sum _{i=1}^n\sum _{j=1}^{m}gcd(i,j{)}^k$$

---

解題思路

$$\sum _{i=1}^n\sum _{j=1}^{m}gcd(i,j{)}^k$$

$$\sum _{d=1}^n{d}^k\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)==d]$$

$$f(x)=\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)==x]$$

$$F(x)=\sum _{x|i}f(i)$$

$$F(x)=?\frac{n}{x}??\frac{m}{x}?$$

$$f(x)=\sum _{x|i}F(x)=\sum _{x|i}\mu (\frac{i}{x})?\frac{n}{i}??\frac{m}{i}?$$

$$\sum _{x=1}^n?\frac{n}{x}??\frac{m}{x}?\sum _{x|i}\mu (\frac{i}{x})i^k$$

然后預處理${\sum }_{x|i}\mu (\frac{i}{x})i^k$的前綴和即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e6+10,XJQ=1e9+7; ll T,k,n,m,cnt,mu[N],g[N],pw[N],pri[N]; bool vis[N]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } void prime(){g[1]=1;for(ll i=2;i<N;i++){if(!vis[i]){pri[++cnt]=i;pw[cnt]=power(i,k);g[i]=(pw[cnt]-1+XJQ)%XJQ;}for(ll j=1;i*pri[j]<N&&j<=cnt;j++){vis[i*pri[j]]=1;if(i%pri[j]==0){g[i*pri[j]]=g[i]*pw[j]%XJQ;break;}g[i*pri[j]]=g[i]*g[pri[j]]%XJQ;}}for(ll i=1;i<N;i++)g[i]=(g[i-1]+g[i])%XJQ;return; } int main() {scanf("%lld%lld",&T,&k);prime();while(T--){scanf("%lld%lld",&n,&m);if(n>m)swap(n,m);ll ans=0;for(ll l=1,r;l<=n;l=r+1){r=min(n/(n/l),m/(m/l));(ans+=(n/l)*(m/l)%XJQ*(g[r]-g[l-1]+XJQ)%XJQ)%=XJQ;}printf("%lld\n",(ans+XJQ)%XJQ);} }

總結

以上是生活随笔為你收集整理的P4449-于神之怒加强版【莫比乌斯反演】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。