LightOJ 1245 Harmonic Number (II)

这题我是找的规律，举个例子：10/1=10，10/2=5，10/3=3，10/4=2，10/5=2，10/6=1，10/7=1，10/8=1，10/9=1，10/10=1。 10/2到10/1都是1，10/3到10/2都是2，10/4到10/3都是3，当10/n到10/(n-1)的时候就开始直接循环枚举，例如10/4到10/3中间只差一个元素，则从10/3往后每个区间就只有一个元素了，对应于这里的3，5，10，也就是在1到3这个区间开始一个个枚举。

#include <cstdio> #include <cstring> typedef long long ll; ll process(int n) { ll pre = n; ll low = 2; ll res = 0; ll inc = 1; while(true) { ll temp = n/low; if(pre-temp == 1) break; res += (pre-temp)*inc; ++inc; ++low; pre = temp; } for(ll i = 1; i <= pre; ++i) res += n/i; return res; } int main() { int t,time = 0; ll n; scanf("%d",&t); while(t--) { ++time; scanf("%lld",&n); ll res = process(n); printf("Case %d: %lld\n",time,res); } return 0; }