题目链接：
首先哦，令n<=m，我们来化简式子：
\[ \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)^k \] 设gcd(i,j)=d，则可以变成这样:\[ \sum_{i=1}^n\sum_{j=1}^md^k\\ \] 把d提到前面去，来枚举d：\[ \sum_{d=1}^nd^k\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor}[gcd(i,j)=1] \] 然后就可以开始套了\[ \sum_{d=1}^nd^k\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor}\sum_{x|i,x|j}\mu(x) \] 然后找到满足条件的x的个数，就可以和前面两个sigma说再见了\[ \sum_{d=1}^nd^k\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor}\mu(x)\lfloor{\frac{n}{dx}}\rfloor\lfloor{\frac{m}{dx}}\rfloor\\ 设T=dx，再来枚举T\\ \sum_{d=1}^nd^k\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor}\mu(\frac{T}{d})\lfloor{\frac{n}{T}}\rfloor\lfloor{\frac{m}{T}}\rfloor\\ \sum_{T=1}^n\lfloor{\frac{n}{T}}\rfloor\lfloor{\frac{m}{T}}\rfloor\sum_{d|T}d^k\mu(\frac{T}{d}) \] 一般的题到这一步就能直接搞了，然而会T，所以我们来继续推：注：以下受大佬的启发，与本人博客差不多
设
\[ f(T)=\sum_{d|T}d^k\mu(\frac{T}{d})\\ g(T)=T^k \] 看！\(f(T)\)是不是\(\mu\)和\(g\)的卷积形式！所以\(f\)是个积性函数!我们来对\(f(x)\)进行讨论，首先我们将\(x\)分解质因数
\[ x=\prod{p_i^{a_i}},p_i\in\mathbb{P}\\ f(x)=\prod{f(p_i^{a_i})}\\ f(p_i^{a^i})=\sum_{d|p_i^{a_i}}d^k\mu(\frac{p_i^{a_i}}{d})\\ 因为p_i是个质数，所以\\ f(p_i^{a_i})=\sum_{j=0}^{a_i}{p_i}^{jk}\mu(p_i^{a_i-j})\\ 再考虑一下\mu的性质，可以得出只有当j=a_i或j=a_i-1时，\mu不为0，于是\\ f(p_i^{a_i})=p_i^{a_ik}-p_i^{(a_i-1)k}\\ p\in\mathbb{P}，于是对于f(xp)，若p|x，则只是多了几个指数而已，那么f(xp)=f(x)*p^k\\ 否则，就是添加了几个质因数，则f(xp)=f(x)*(p^k-1) \]Code:
#include#define int long longusing namespace std;const int N=5e6+1;const int pps=1e9+7;int n,m,k,t,tot;int pri[N],mu[N],vis[N],p[N],f[N];int quick(int a,int b){ int sum=1; while(b){ if(b&1) sum*=a,sum%=pps; a=(a*a)%pps,b>>=1; }return sum%pps;}void prepare(){ f[1]=1; for(int i=2;i<=N;i++){ if(!vis[i]) pri[++tot]=i,p[tot]=quick(i,k),f[i]=p[tot]-1; for(int j=1;j<=tot&&pri[j]*i<=N;j++){ vis[i*pri[j]]=1; if(!(i%pri[j])){ f[i*pri[j]]=f[i]*p[j]%pps; break; }f[i*pri[j]]=f[i]*(p[j]-1)%pps; } }for(int i=1;i<=N;i++) f[i]=(f[i]+f[i-1])%pps;}int calc(int n,int m){ int d=1,sum=0; while(d<=n&&d<=m){ int pre=d;d=min(n/(n/d),m/(m/d)); sum=(sum+(n/d)*(m/d)%pps*(f[d]-f[pre-1])%pps)%pps; ++d; }return (sum+pps)%pps;}int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();} while(isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f;}signed main(){ t=read(),k=read(); prepare(); while(t--){ n=read(),m=read(); printf("%lld\n",calc(n,m)); } return 0;}