UVa 11526 – H(n)

这道题学校里的班级程序设计对抗赛决赛中就有这题,当时貌似只有一个人A出来,一头雾水,不知如何下手。其实现在看看AC的思路,当时还是飘出过来的,就是没有信心,按照这个思路写下去。

思路就是找到所有n/i结果相同的区间[i, j],这样就省出不少时间了,不然会超时。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
inline LL H(LL n)
{
    LL res = 0;
    for(LL i = 1, j; i <= n; i = j + 1){
        j = n / (n / i);
        res += (j - i + 1) * (n / i);
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while(T--){
        LL n; cin >> n;
        cout << H(n) << endl;
    }
    return 0;
}

 

欢迎留言