整除分块裸题.
在BZOJ 1257-余数之和里有应用过,推理部分也在那篇文章里,或者直接看《算法竞赛进阶指南》P139.
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;
long long H( int n ) {
long long res = 0;
int len;
for( long long i = 1; i <= n; i+=len ){
len=n/(n/i)-i+1;
res = res + (n / i)*len;
}
return res;
}
int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T,kase=0;
cin>>T;
while(T--){
int n;
cin>>n;
printf("Case %d: %lld\n",++kase,H(n));
}
return 0;
}