Function

题目链接

题意

计算

$$\sum_{i = 1}^{n} gcd( \left \lfloor \sqrt[3]{i} \right \rfloor, i).$$

对$998244353$取模。$1 \leq n \leq {10}^{21}.$

思路

$$ans = \sum_{i = {r}^{3} }^{n} gcd(i, \left \lfloor \sqrt[3]{n} \right \rfloor ) + \sum_{a=1}^{r-1} \sum_{i={a}^{3} }^{ {(a+1)}^{3}-1}gcd(i, {a}^{3}).$$ $$\sum_{i=1}^{n}gcd(i, a) = \sum_{d=1}^{n} d \sum_{i=1}^{n}[gcd(i, a) = d].$$ $$= \sum_{d|a} d \sum_{i=1}^{ \frac{n}{d} } [gcd(i, \frac{a}{d}) = 1]$$ $$= \sum_{d|a} d \sum_{i=1}^{ \frac{n}{d} } \mu(i) \left \lfloor \frac{n}{di} \right \rfloor$$ $$= \sum_{d|a} d \sum_{T|a, d|T} \mu( \frac{T}{d} ) \left \lfloor \frac{n}{T} \right \rfloor$$ $$= \sum_{T|a} \left \lfloor \frac{n}{T} \right \rfloor \sum_{d|T} d \mu( \frac{T}{d})$$ $$= \sum_{T|a} \left \lfloor \frac{n}{T} \right \rfloor \varphi(T).$$ $$\sum_{a=1}^{x} \sum_{i={a}^{3} }^{ {(a+1)}^{3} - 1} gcd(i,{a}^{3})$$ $$= \sum_{a=1}^{x} \sum_{T|a} \varphi(T) ( \left \lfloor \frac{ {(a+1)}^{3}-1}{T} \right \rfloor - \left \lfloor \frac{ {a}^{3} - 1}{T} \right \rfloor)$$ $$= \sum_{T=1}^{x} \varphi(T) \sum_{i=1}^{ \left \lfloor \frac{x}{T} \right \rfloor} \left \lfloor \frac{ {(iT+1)}^{3}-1}{T} \right \rfloor - \left \lfloor \frac{ {(iT)}^{3}-1}{T} \right \rfloor$$ $$= \sum_{T=1}^{x} \varphi(T) \sum_{i=1}^{ \left \lfloor \frac{x}{T} \right \rfloor} 3T{i}^{2}+3i+1.$$

复杂度$O( \sqrt[3]{n})$。