zoj 3175 Number of Containers 分块加快

zoj 3175 Number of Containers 分块加速

题意：计算n以内i的倍数的个数，不包括i本身，求和

解：直接暴力for一遍一定是不行的，不过用一个分块加速就可以了

#include <stdio.h>
#include <string.h>
int main()
{
    int t;
    long long n;
    while(scanf("%d",&t)!=-1)
    {
        while(t--)
        {
            scanf("%lld",&n);                  //要用lld错了N发的教训
            long long sum=0;
            for(int i=1,last;i<=n;i=last+1)
            {
                last=n/(n/i);                 //分块加速，所有n/i结果相同的一起计算
                sum+=((n/i-1)*(last-i+1));
            }
            printf("%lld\n",sum);
        }
    }
    return 0;
}