【bzoj2956】模积和 数论分块

• linda_si 发布于
• 1363 收藏

额，终于把图片搞出来了。 这个式子处理起来是O(n)的，但是我们发现n/i只用O(√n)个取值，我们枚举这O(√n)个取值。 假如枚举的取值为k，则把所有n/i=k的i求和即可 (k+1)*i>n>=k*i 所以i的取值区间为[n/(k+1)+1,n/k] 但是我们循环的时候枚举的是i，而不是k，每一次把i变成上一次的取值+1就可以了。 最后的那个式子也不难，就是一共有O(√n+√m)个取值，有用...