NEU1403

题目链接

题意：求[n/1]+[n/2]+[n/3]+..+[n/n]。

直接暴力会超时，我们采用枚举商的做法。

以 n=15 为例，

i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

n/i 15 7 5 3 3 2 2 1 1 1 1 1 1 1 1

用 l 和 r 来代表每次枚举商的两侧端点，不断更新。找找规律就好。

比如说一开始 l=r=n，n/2=7，更新 l 为 7，那么 r-l 这段内是同一个数，这个数是 n/(l+1).

除以 2 之后应该除以什么呢？这个地方是关键，经过观察应是这个除数应是 n/l+1。因为只有这样才能保证 l 最后一直更新到 1。

#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
using namespace std;

int main(){
    //freopen("a.txt", "r", stdin);
    int n, t; cin >> t;
    for(int cas = 1; cas <= t; cas++){
        scanf("%d", &n);
        long long l = n, r = n, ans = 0, x = 2;
        while(l != 1){
            l = n/x;
            x = n/l+1;
            ans += (n/(l+1))*(r-l);
            r = l;
            //cout << ans << endl;
        }

        printf("Case%d: %lldn", cas, ans+n);
    }
    return 0;
}