题目大意：
让你求：$\sum_{i = 1}^ngcd(\lfloor\sqrt[3]{n}\rfloor,i) \mod 998322353$∑i=1n​gcd(⌊3n​⌋,i)mod998322353

$n \leq 10 ^ {21}$n≤1021

---

题解：
明显可以按$\sqrt[3]{n}$3n​分块，将式子拆成两部分：$\sum_{T = 1}^{\lfloor\sqrt[3]{n}\rfloor - 1}\sum_{i = T^3}^{(T + 1)^3 - 1} gcd(T,i) + \sum_{i = \lfloor\sqrt[3]{n}\rfloor}^ngcd(\lfloor\sqrt[3]{n}\rfloor,i)$T=1∑⌊3n​⌋−1​i=T3∑(T+1)3−1​gcd(T,i)+i=⌊3n​⌋∑n​gcd(⌊3n​⌋,i)反演右边：$\sum_{i = l}^rgcd(a,i) = \sum_{d | a}\sum_{i = l}^rd * [gcd(a,i) = d]$i=l∑r​gcd(a,i)=d∣a∑​i=l∑r​d∗[gcd(a,i)=d]$=\sum_{i = l}^rgcd(a,i) = \sum_{d | a}d\sum_{i = \lceil\frac{l}{d}\rceil}^{\lfloor\frac{r}{d}\rfloor}[gcd(\frac{a}{d},i) = 1]$=i=l∑r​gcd(a,i)=d∣a∑​di=⌈dl​⌉∑⌊dr​⌋​[gcd(da​,i)=1]$=\sum_{d | a}d\sum_{i = \lceil\frac{l}{d}\rceil}^{\lfloor\frac{r}{d}\rfloor}\sum_{p | \frac{a}{d},p|i}\mu(p)=\sum_{d | a}d\sum_{p | \frac{a}{d}}\mu(p)\sum_{i = \lceil\frac{l}{d * p}\rceil}^{\lfloor\frac{r}{d * p}\rfloor}$=d∣a∑​di=⌈dl​⌉∑⌊dr​⌋​p∣da​,p∣i∑​μ(p)=d∣a∑​dp∣da​∑​μ(p)i=⌈d∗pl​⌉∑⌊d∗pr​⌋​$=\sum_{T | a}\sum_{d | T}d*\mu(\frac{T}{d})({\lfloor\frac{r}{T}\rfloor} - {\lfloor\frac{l - 1}{T}\rfloor})$=T∣a∑​d∣T∑​d∗μ(dT​)(⌊Tr​⌋−⌊Tl−1​⌋)$=\sum_{T | a}\phi(T)*({\lfloor\frac{r}{T}\rfloor} - {\lfloor\frac{l - 1}{T}\rfloor})$=T∣a∑​ϕ(T)∗(⌊Tr​⌋−⌊Tl−1​⌋)于是右边可以在$\sqrt[6]n$6n​时间内求出
反演左边
（这里用个小技巧，不用莫比乌斯反演，直接应用欧拉函数的性质：$\sum_{d|x}\phi(d) =x$∑d∣x​ϕ(d)=x）：$\sum_{T = 1}^{\lfloor\sqrt[3]{n}\rfloor - 1}\sum_{i = T^3}^{(T + 1)^3 - 1} gcd(T,i)$T=1∑⌊3n​⌋−1​i=T3∑(T+1)3−1​gcd(T,i)$=\sum_{T = 1}^{\lfloor\sqrt[3]{n}\rfloor - 1}\sum_{i = T^3}^{(T + 1)^3 - 1} \sum_{p|gcd(T,i)}\phi(p)$=T=1∑⌊3n​⌋−1​i=T3∑(T+1)3−1​p∣gcd(T,i)∑​ϕ(p)$=\sum_{T = 1}^{\lfloor\sqrt[3]{n}\rfloor - 1} \sum_{p|T}\phi(p)\sum_{i = \lceil\frac{T^3}{p}\rceil}^{\lfloor\frac{(T + 1)^3 - 1}{p}\rfloor}$=T=1∑⌊3n​⌋−1​p∣T∑​ϕ(p)i=⌈pT3​⌉∑⌊p(T+1)3−1​⌋​$=\sum_{T = 1}^{\lfloor\sqrt[3]{n}\rfloor - 1} \sum_{p|T}\phi(p)({\lfloor\frac{(T + 1)^3 - 1}{p}\rfloor} - {\lfloor\frac{{T }^3 - 1}{p}\rfloor})$=T=1∑⌊3n​⌋−1​p∣T∑​ϕ(p)(⌊p(T+1)3−1​⌋−⌊pT3−1​⌋)$=\sum_{p = 1}^{\lfloor\sqrt[3]{n}\rfloor - 1}\phi(p)\sum_{T = 1}^{\lfloor\frac{\lfloor\sqrt[3]{n}\rfloor - 1}{p}\rfloor}({\lfloor\frac{(T *p+ 1)^3 - 1}{p}\rfloor} - {\lfloor\frac{({T*p })^3 - 1}{p}\rfloor})$=p=1∑⌊3n​⌋−1​ϕ(p)T=1∑⌊p⌊3n​⌋−1​⌋​(⌊p(T∗p+1)3−1​⌋−⌊p(T∗p)3−1​⌋)$=\sum_{p = 1}^{\lfloor\sqrt[3]{n}\rfloor - 1}\phi(p)\sum_{T = 1}^{\lfloor\frac{\lfloor\sqrt[3]{n}\rfloor - 1}{p}\rfloor}({(T^3 *p^2+ 3*T^2*p+3*T) } - ({T^3*p^2 } - 1))$=p=1∑⌊3n​⌋−1​ϕ(p)T=1∑⌊p⌊3n​⌋−1​⌋​((T3∗p2+3∗T2∗p+3∗T)−(T3∗p2−1))$=\sum_{p = 1}^{\lfloor\sqrt[3]{n}\rfloor - 1}\phi(p)\sum_{T = 1}^{\lfloor\frac{\lfloor\sqrt[3]{n}\rfloor - 1}{p}\rfloor}(3*T^2*p+3*T + 1)$=p=1∑⌊3n​⌋−1​ϕ(p)T=1∑⌊p⌊3n​⌋−1​⌋​(3∗T2∗p+3∗T+1)
$\sum_{i = 1}^n i = \frac{i * (i + 1)}{2},\sum_{i = 1}^ni^2 = \frac{i*(i + 1)*(2*i + 1)}{6}$∑i=1n​i=2i∗(i+1)​,∑i=1n​i2=6i∗(i+1)∗(2∗i+1)​
线性筛预处理一下$\phi(i) * i 和 \phi(i)$ϕ(i)∗i和ϕ(i)的前缀和
将式子分成三部分后分块做（也可以直接暴力，因为组数比较少）
复杂度$O(\sqrt[3]n + T * \sqrt[6]n)$O(3n​+T∗6n​)

---

#include<bits/stdc++.h>
using namespace std;
#define int128 __int128
const int maxn = 1e7 + 10;
const int mod = 998244353;
typedef long long ll;
inline __int128 read() {
 	__int128 x=0,f=1;
 	char ch=getchar();
 	while(ch<'0'||ch>'9') {
 		if(ch=='-')
 			f=-1;
 		ch=getchar();
 	}
 	while(ch>='0'&&ch<='9') {
 		x=x*10+ch-'0';
 		ch=getchar();
 	}
 	return x*f;
}
void print(__int128 x)
{
	if (!x) return ;
	if (x < 0) putchar('-'),x = -x;
	print(x / 10);
	putchar(x % 10 + '0');
}
bool ispri[maxn];
int pri[maxn],phi[maxn],t;
ll sum[maxn];
ll val[maxn];
__int128 n;
void sieve(int n) {
	ispri[0] = ispri[1] = true;
	phi[1] = 1;pri[0] = 0;
	for(int i = 2; i <= n; i++) {
		if(!ispri[i]) pri[++pri[0]] = i,phi[i] = i - 1;
		for(int j = 1; j <= pri[0] && i * pri[j] <= n; j++) {
			ispri[i * pri[j]] = true;
			if(i % pri[j] == 0) {
				phi[i * pri[j]] = phi[i] * pri[j];
				break;
			}
			phi[i * pri[j]] = phi[i] * (pri[j] - 1);
		}
	}
	sum[0] = val[0] = 0;
	for(int i = 1; i <= n; i++)
		sum[i] = (sum[i - 1] + 1ll * phi[i] * i % mod) % mod;
	for(int i = 1; i <= n; i++)
		val[i] = (val[i - 1] + phi[i]) % mod;
}
ll inv2,inv6;
ll fpow(ll a,ll b) {
	ll r = 1;
	while(b) {
		if(b & 1) r = r * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return r;
}
ll cal1(ll x) {
	x %= mod;
	return x * (x + 1) % mod * (x + x + 1) % mod * inv6 % mod;
}
ll cal2(ll x) {
	x %= mod;
	return x * (x + 1) % mod * inv2 % mod;
}
int main() {
	sieve(10000000);
	inv2 = fpow(2,mod - 2);
	inv6 = fpow(6,mod - 2);
	scanf("%d",&t);
	while(t--) {
		n = read();
		if(n <= 7) {
			printf("%d\n",(int)n);
			continue;
		}
		int r = 1;
		for(r = 1; (__int128)(r + 2) * (r + 2) * (r + 2) - 1 <= n; r++);
		int i,j;
		ll res = 0;
		for(i = 1; i <= r; i = j + 1) {
			j = r / (r / i);
			res = (res + (sum[j] - sum[i - 1] + mod) % mod * 3 % mod * cal1(r / i) % mod) % mod;
			res = (res + (val[j] - val[i - 1] + mod) % mod * 3 % mod * cal2(r / i) % mod) % mod;
			res = (res + (val[j] - val[i - 1] + mod) % mod * (r / i) % mod) % mod;
		}
		ll a = r + 1;
		__int128 L = (__int128)a * a * a - 1;
		for(int i = 1; 1ll * i * i <= a; i++) {
			if(a % i == 0) {
				ll t = (n / i - L / i) % mod;
				res = (res + 1ll * phi[i] * t % mod) % mod;
				if(a / i != i) {
					ll t = (n / (a / i) - L / (a / i)) % mod;
					res = (res + 1ll * phi[a / i] * t % mod) % mod;
				}
			}
		} 
		printf("%lld\n",res);
	}
	return 0;
}