如果像我一样不知道积性函数啥的，这里提供一种比较优雅的暴力方法 众所周知，下面这个倍数遍历的代码复杂度是O(nlogn)

for (i = 1; i <= n; i++)
{
	for (j = i; j <= n; j += i)
	{
		//todo
	}
}

那么，因为欧拉函数和唯一分解定理的推论都是由质数表现的，那么对质数进行倍数遍历，然后对每一个质数的倍数进行贡献叠加起来就行 时间复杂度O(nlogn^2) 实际上，可以通过预处理等被把一层的log给优化掉，但是太懒，并且能过题，就没优化，大家可以试试优化下

void solve()
{
	
	ff(1e6);
	cin >> n >> k;
	ll i, j, ans = 0;
	for (i = 1; i <= n; i++) e[i] = qpow(i, k), h[i] = 1;
	for (auto i : pri)
	{
		for (j = i; j <= n; j += i)
		{
			e[j] = ((e[j] * (i - 1) % mod) * qpow(i, mod - 2)) % mod;
			ll t = j, cnt = 0;
			while (t % i == 0) cnt++, t /= i;
			h[j] = h[j] * (qpow(i, cnt * k + 1) - 1 + mod) % mod * qpow(i - 1, mod - 2);
			h[j] %= mod;
		}
		
	}
	for (i = 1; i <= n; i++)
		ans = ans + (h[i] * e[i] % mod), ans %= mod;
	cout << ans << endl;
}

我就是队里不会数论的那个人(逃