题目链接P4449 于神之怒加强版
题目大意：求
\[\sum _{i=1}^{n}\sum _{j=1}^{m}gcd(i,j)^k \]\(数据范围n,m\leq5e6\)
\(二话不说，先开导式子(假定n<m)：\)
\begin{aligned}
ans&=\sum _{i=1}^{n}\sum _{j=1}^{m}gcd(i,j) ^k\\
\end{aligned}
\begin{aligned}
ans&=\sum _{i=1}^{n}\sum _{j=1}^{m}\sum _{d=1}^{n}d ^k(d=gcd(i,j))
\end{aligned}
\begin{aligned}
ans&=\sum _{d=1}^{n}\sum _{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum _{j=1}^{\lfloor{\frac{m}{d}}\rfloor}d ^k(gcd(i,j)=1)\\
ans&=\sum _{d=1}^{n}\sum _{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum _{j=1}^{\lfloor{\frac{m}{d}}\rfloor}d ^k\sum _{e|gcd(i,j)}u(e)\\
ans&=\sum _{d=1}^{n}\sum _{e=1}^{\lfloor{\frac{n}{d}}\rfloor}{\lfloor{\frac{n}{de}}\rfloor}{\lfloor{\frac{m}{de}}\rfloor}d ^ku(e)\\
\end{aligned}
\begin{aligned}
ans&=\sum _{T=1}^{n}\sum _{d|T}\lfloor{\frac{n}{T}}\rfloor \lfloor{\frac{m}{T}}\rfloor d ^ku(\frac{T}{d})
\end{aligned}
\begin{aligned}
ans&=\sum _{T=1}^{n}\lfloor{\frac{n}{T}}\rfloor \lfloor{\frac{m}{T}}\rfloor\sum _{d|T} d ^ku(\frac{T}{d})
\end{aligned}
\begin{aligned}
设op=p^{x+1},则有\\
g(op)=\sum _{d|op} d ^ku(\frac{op}{d})
\end{aligned}
最后就是代码了：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e6+5,p=1e9+7;
int n,m,k,t,x,y,z;
int s[N],f[N];
int prime[N],tot;
bool not_prime[N];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=ans*a%p;
a=a*a%p;
b>>=1;
}return ans;
}
void iint(){
f[1]=1;
for(int i=2;i<=5000000;i++){
if(!not_prime[i])prime[++tot]=i,f[i]=(qpow(i,k)-1+p)%p;
for(int j=1;j<=tot&&i*prime[j]<=5000000;++j){
not_prime[i*prime[j]]=1;
if(i%prime[j]==0){
f[prime[j]*i]=(f[i]*((f[prime[j]]+1)%p))%p;
break;
}
f[i*prime[j]]=f[i]*f[prime[j]]%p;
}
}
for(int i=1;i<=5000000;i++)s[i]=(s[i-1]+f[i])%p;
}
int get(int n,int m){
int ans=0;
if(n>m)swap(n,m);
for(int l=1,r=1;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
ans=(ans+(s[r]-s[l-1]+p)%p*(n/l)%p*(m/l)%p)%p;
}return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>t>>k;
iint();
while(t--){
cin>>n>>m;
cout<<get(n,m)<<endl;
}
return 0;
}