大意: 给定$n(n\le 10^{21})$, 求$\sum\limits_{i=1}^n gcd(\lfloor\sqrt[3]{i}\rfloor,i)\mod 998244353$

 

首先立方根可以分块, 转化为

$\sum\limits_{i=1}^{\lfloor\sqrt[3]{n}\rfloor}\sum\limits_{j=i^3}^{min(n,(i+1)^3-1)}gcd(i,j)=\sum\limits_{i=\lfloor\sqrt[3]{n}\rfloor^3}^ngcd(r+1,i)+\sum\limits_{i=1}^r\sum\limits_{j=i^3}^{(i+1)^3-1}gcd(i,j)$

然后有$\sum\limits_{i=1}^n gcd(S,i)=\sum\limits_{d|S}\lfloor\frac{n}{d}\rfloor\varphi(d)$, 所以可以得到

$\begin{align}\sum\limits_{i=1}^r\sum\limits_{j=i^3}^{(i+1)^3-1}gcd(i,j) &=\sum\limits_{i=1}^r\sum\limits_{d|i}(\lfloor\frac{(i+1)^3-1}{d}\rfloor-\lfloor\frac{i^3-1}{d}\rfloor)\varphi(d) \notag \\ &= \sum\limits_{d=1}^r\sum\limits_{i=1}^{\lfloor\frac{r}{d}\rfloor}(\lfloor\frac{(di+1)^3-1}{d}\rfloor-\lfloor\frac{(di)^3-1}{d}\rfloor) \notag \\ &= \sum\limits_{d=1}^r\varphi(d)\sum\limits_{i=1}^{\lfloor\frac{r}{d}\rfloor}(3di^2+3i+1)\notag\end{align}$

可以$O(\sqrt[3]{n})$求出.

#include 
     
      #include 
      
       #include 
       
        #define REP(i,a,n) for(int i=a;i<=n;++i)using namespace std;typedef long long ll;typedef __int128 i128;template 
        
         void read(T &x) {	static char ch;static bool neg;	for(ch=neg=0;ch<'0' || '9'