bzoj1257(SPOJ-NAGAY Joseph’s Problem(余数求和))（分块）

这个博客写的很详细。 http://blog.csdn.net/braketbn/article/details/50715971 看图会发现规律（图是盗的）：

看了很久我才明白，mdzz。 设k = d * x + r。发现每个块内都是一个等差数列，公差就是d。 其实原理很简单, 假设x是使k/x=d的最小整数,(当然，向下取整) 写成k=d* x+r, 如果r>d,那么就会有k=d* (x+1)+r-d, 如果r>2d,那么就会有k=d* (x+2)+r-2d, 所以等差数列的第一项是k-d*x即k%x. 最后一项就应该是k-d*y即k%y。 其中y是使k/y=d的最大整数（当然，向下取整）。

因为此时k=d*y+r (r必定 < d)。 于是我们枚举d，按d分块。（这里其实是枚举等差数列的第一项，第一项确定，d也跟着确定） 对于一个块[L, R]（指的是i的区间），显然R = k / d，那么d怎么求呢？ (L=k/(d+1）+1，这里其实就是i) 首先i从1（第一次必定满足i是使k/x=d的最小整数）开始, d=k/i， r=(k/d) 然后i=r+1（保证下一次时i也满足i是使k/x=d的最小整数），接着代码。。。。 注意：求出来的r不能大于n

#include <stdio.h> typedef unsigned long long ULL; int main(int argc, char const *argv[]) { ULL n,k,ans=0; scanf("%llu %llu",&n,&k); for(ULL i=1,r;i<=n;i=r+1) { ULL d=k/i; r=d?(k/d):n; r=(r>n)?n:r; ans+=(k-i*d+k-r*d)*(r-i+1)/2;//k-i*d相当于k%i } printf("%llu\n",ans ); return 0; }