rt，赛时调了 1h 没调出来

代码：

// superyijin AK IOI
// wangsiyuanZP AK IOI
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int ksm(int a, int b)
{
	int t = 1;
	while (b)
	{
		if (b & 1) t = t * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return t;
}
int fac[70], invfac[70];
int C(int n, int m)
{
	return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
map<int, map<int, int>> dp;
int f(int n, int k)
{
	n %= mod;
	if (k == 0) return n;
	if (dp[n][k]) return dp[n][k];
	int s = ksm(n + 1, k + 1) - 1;
	for (int i = 0; i < k; i++) s = (s - C(k + 1, i) * f(n, i) % mod + mod) % mod;
	s = s * ksm(k + 1, mod - 2) % mod;
	return dp[n][k] = s;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	fac[0] = 1;
	for (int i = 1; i <= 64; i++) fac[i] = fac[i - 1] * i % mod;
	invfac[64] = ksm(fac[64], mod - 2);
	for (int i = 63; i >= 0; i--) invfac[i] = invfac[i + 1] * (i + 1) % mod;
	int t;
	cin >> t;
	while (t--)
	{
		int n, d;
		cin >> n >> d;
		vector<pair<int, int>> v;
		int mx = 0;
		for (int i = 2; i * i <= d; i++)
		{
			if (d % i != 0) continue;
			int cnt = 0;
			while (d % i == 0) d /= i, cnt++;
			v.push_back(make_pair(i, cnt));
			mx = max(mx, cnt);
		}
		if (d > 1)
		{
			v.push_back(make_pair(d, 1));
			mx = max(mx, 1ll);
		}
		int ans = f(n, 1), lst = n + 1;
		for (int i = 1; i <= mx; i++)
		{
			int mul = 1;
			for (auto j : v)
			{
				int p = (j.second + i - 1) / i;
				for (int k = 1; k <= p; k++) mul *= j.first;
			}
			int k1 = f(n / mul, i + 1), k2 = f(n / lst, i + 1);
			ans = (ans + (ksm(mul, i + 1) * k1 - mul % mod * f(n / mul, 1)) % mod - (ksm(lst, i + 1) * k2 - lst % mod * f(n / lst, 1)) % mod + mod + mod) % mod;
			lst = mul;
		}
		cout << ans << '\n';
	}
	return 0;
}
// superyijin AK IOI
// wangsiyuanZP AK IOI