题目链接
思路： 先打一个从1到1e6的素数表，然后枚举不超过 r√ 的所有素数，然后再去枚举这些素数在l和r区间内的倍数，将其分解质因数，最后剩下的素数的c只可能是0或1，计算出每个数对应的因子个数，对于每个数的因子个数就等于枚举的因子个数*k+1累乘起来，最后加起来即可。 代码
# include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e6+10; const int Q = 998244353; LL cnt [N], q[N], prime[N]; bool vis[N]; void init () { int tot = 0; for (int i=2; i<=N; ++i) { if (!vis[i]) { prime[tot++] = i; } for (int j=0; j<tot; ++j) { int k = i * prime[j]; if (k > N) break; vis[k] = 1; } } } void solve () { LL l, r, k, ans = 0; scanf("%lld%lld%lld", &l, &r, &k); if (l == 1) ans ++, l++; for (LL i = 0; i <= r-l; ++i) { cnt[i] = 1, q[i] = l+i; } for (LL i = 0; prime[i] * prime[i] <= r; ++i) { LL x = l / prime[i] + (l % prime[i] != 0); for (x *= prime[i]; x <= r; x += prime[i]) { LL cou = 0; while (q[x - l] % prime[i] == 0) { q[x - l] /= prime[i], cou++; } cnt [x - l] = (cnt [x - l] * ((cou * k) + 1)) % Q; } } for (LL i=0; i<=r-l; ++i) { if (q[i] != 1) ans = (ans + (k+1) * cnt[i]) % Q; else ans = (ans + cnt[i]) % Q; } printf ("%lld\n", ans); } int main () { int T; init (); scanf ("%d", &T); while (T--) { solve (); } return 0; }