趣题

在OJ上瞎逛，记录两道趣题。 超级mod 定义 f[i]=(((i%a[0])%a[1])%...)%a[m−1]) 快速求解 f[1]+...+f[n] 。 仔细的话可以发现这就相当于区间分割，对于 a[0] 来说，把区间 [1,n] 分成若干个 [1,a[0]−1] 和一个 [1,n%a[0]] ，同理下面的是一样的。那样处理 a[i] 后只需处理 a[j]<a[i] ，我们直接分块统计即可。 实际上时间复杂度是很低的估计是 O(T∗m∗log(m)) 。

LCM 求解最小的 N 使得lcm(A N,B N)最小。 发现与 AB 的差 d 有关，也就是说gcd(A N,B N)是 d <script type="math/tex" id="MathJax-Element-1640">d</script>的因子。 枚举因子即可。 不过坑的是，在出题人眼里自然数是不包含0的 ，注意。(ˇˍˇ) 想～