NEU1403 XL’s Math Problem II(数学)

题目链接

题意:求[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;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 数学