Description：

$\begin{align}\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)^k\end{align}$

$1\le n,m\le 5000000$

Solution：

反演得： $\begin{align}\sum_{T=1}^{min(n,m)}\lfloor\frac n T\rfloor\lfloor\frac m T\rfloor\sum_{d|T}d^k\mu(\frac T d)\end{align}$

题目要求线性，考虑怎么筛 $g(x)=\sum_{d|x}d^k\mu(\frac x d)$

首先积性。 $g(1)=1$ ， $g(p)=p^k-1$ 。

当 $i\%prime[j]==0$ 时，对于一个因子 $d$ 如果他只出现一次，贡献为 $d^k\times 1+1^k\times(-1)=d^k-1$

如果出现多次，只有 $\mu(1)$ 和 $\mu(p^q)$ 再 $\mu$ 的容斥下能留下来所以对于一个因子只有 $\mu(1)$ 和 $\mu(p^q)$ 有值，于是可以累加了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int testcases;

int n,m,k;

typedef long long ll;

#define MAXN 5000010

#define MOD 1000000007

int prime[MAXN],tot = 0,mu[MAXN];

ll g[MAXN],idk[MAXN];

bool isprime[MAXN];

ll powk(int p)

{

	if(idk[p] != 0)return idk[p];

	ll res = 1,a = (ll)p,b = k;

	while(b > 0)

	{

		if(b & 1)res = (res * a) % MOD;

		a = (a * a) % MOD;

		b = b >> 1;

	}

	return res;

}

void sieve()

{

	for(int i = 2;i < MAXN;++i)isprime[i] = true;

	mu[1] = 1;g[1] = 1;idk[1] = 1;

	for(int i = 2;i < MAXN;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			mu[i] = -1;

			idk[i] = powk(i);

			g[i] = (idk[i] - 1 + MOD) % MOD;

		}

		for(int j = 1;j <= tot && i * prime[j] < MAXN;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)

			{

				g[i * prime[j]] = g[i] * powk(prime[j]) % MOD;

				break;

			}

			else

			{

				g[i * prime[j]] = g[i] * g[prime[j]] % MOD;

			}

		}

	}

	for(int i = 1;i < MAXN;++i)

	{

		g[i] = (g[i] + g[i - 1]) % MOD;

	}

	return;

}

int main()

{

	scanf("%d%d",&testcases,&k);

	sieve();

	for(int i = 1;i <= testcases;++i)

	{

		scanf("%d%d",&n,&m);

		int end = min(n,m);

		ll ans = 0;

		for(int l = 1,r = 0;l <= end;l = r + 1)

		{

			r = min(n / (n / l),m / (m / l));

			ans += (g[r] - g[l - 1] + MOD) % MOD * (ll)(n / l) % MOD * (ll)(m / l) % MOD;

			ans %= MOD;

		}

		cout << ans << endl;

	}

	return 0;

}