LightOJ – 1245 Harmonic Number (II)

LightOJ – 1245

整除分块裸题.

在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;
}