Statement
\(S(n,m)=\{k\mid k\in\mathbb N^+\land n\bmod k+m\bmod k\ge k\}\)，求 \(\varphi(n)\varphi(m)\sum_{k\in S(n,m)}k\pmod{998244353}\)（\(n,m\le10^{15}\)）
Solution
欧拉函数怎么求就不说了，可以 \(\mathcal O(\sqrt n)\) 解决
\(n\bmod k+m\bmod k\ge k\) 相当于 \(\left\lfloor\dfrac nk\right\rfloor+\left\lfloor\dfrac mk\right\rfloor=\left\lfloor\dfrac{n+m}k\right\rfloor-1\)
即 \(\left\lfloor\dfrac nk\right\rfloor+\left\lfloor\dfrac mk\right\rfloor+1=\left\lfloor\dfrac{n+m}k\right\rfloor\)
因为 \(\left\lfloor\dfrac nk\right\rfloor\) 和 \(\left\lfloor\dfrac nk\right\rfloor\) 和 \(\left\lfloor\dfrac{n+m}k\right\rfloor\) 最多 \(\sqrt n\) 种（1e15+1e15=2e15），直接大力整除分块，还是 \(\mathcal O(\sqrt n)\)，能过
标签：lfloor,right,题解,bmod,rfloor,问题,模数,dfrac,left From： https://www.cnblogs.com/laijinyi/p/18148199