题给代码意为
\[\begin{align*} &\sum\limits_{i = 1}^n \sum\limits_{j = 1}^{\lfloor \frac n i \rfloor} \sum\limits_{k = 1}^j [\gcd(j, k) = 1] \\ = &\sum\limits_{i = 1}^n \sum\limits_{j = 1}^{\lfloor \frac n i \rfloor} \varphi(j) \\ \end{align*} \]设
\[S(n) = \sum\limits_{i = 1}^n \varphi(i) \]则答案为
\[\sum\limits_{i = 1}^n S \left( \left\lfloor \frac n i \right\rfloor \right) \]发现它很像杜教筛式子
\[S(n) = \frac 1 2 n (n + 1) - \sum\limits_{i = 2}^n S \left( \left\lfloor \frac n i \right\rfloor \right) \]所以直接代入，答案为
\[\begin{align*} &\sum\limits_{i = 1}^n S \left( \left\lfloor \frac n i \right\rfloor \right) \\ = &S(n) + \sum\limits_{i = 2}^n S \left( \left\lfloor \frac n i \right\rfloor \right) \\ = &\frac 1 2 n (n + 1) - \sum\limits_{i = 2}^n S \left( \left\lfloor \frac n i \right\rfloor \right) + \sum\limits_{i = 2}^n S \left( \left\lfloor \frac n i \right\rfloor \right) \\ = &\frac 1 2 n (n + 1) \\ \end{align*} \]时间复杂度 \(O(\lg n)\)。
#include <iostream>
#define int long long
using namespace std;
const int mod = 998244353;
const int _2 = 499122177;
static inline int read() {
int x = 0;
char ch = cin.get();
while (!isdigit(ch))
ch = cin.get();
while (isdigit(ch)) {
x = ((x << 3) + (x << 1) + (ch ^ 48)) % mod;
ch = cin.get();
}
return x;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
int n = read();
cout << n * (n + 1) % mod * _2 % mod << endl;
}
return 0;
}