Solution UVA: 11526 - H(n)

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11526 - H(n)	Accepted	C++11	0.270	0.020	1461	1 mins ago

Source solution: http://using-c.blogspot.com/

「for n = 10; go along the similar way:

lets say n = 10;
k = 1; sum = 0;
so, 10/1 = 10

k = 2
and 10/2 = 5
so, for all the integer divisions, all i = 6 to 10
will produce n/i = 1; (last denominator)
so, you don't need to calculate for 6 to 10, you have
5x1 + 10/1 = 15; (for k = 1) sum = 15;

k = 3
again 10/3 = 3
so, for all the integer divisions, all i = 4 to 5
will produce n/i = 2; (last denominator)
so, you don't need to calculate for 4 to 5, you have
2x2 + 10/2 = 9; (for k = 2) sum = sum + 9 = 24;

as k is the largest within sqrt(10);
so last we count for k = 3; for 3, one thing here to
note that, 10/3 is also 3,
so, in such cases, we have to consider once, cause
otherwise it will be counted twice.
so, sum = sum + 3 = 27(ans)

for 10, we have the values (imagine RED is not yet
counted, and GREEN is already counted, and BLUE is
the current term)
k = 1; (10) + 5 + 3 + 2 + 2 + (1 + 1 + 1 + 1 + 1)
k = 2; 10 + (5) + 3 + (2 + 2) + 1 + 1 + 1 + 1 + 1
k = 3; 10 + 5 + (3) + 2 + 2 + 1 + 1 + 1 + 1 + 1;
so you see, 3 is to be counted once as it
has no separate counterpart.
if k==n/k then you need to count once;」

#include<bits/stdc++.h>

#define int long long

using namespace std;

int H(int n){

    int res = 0;

    for(int i = 1; i*i <= n; i++){

        int cnt= (n/i) - (n/(i+1));

        if (n/i==i) res += n/i;

            else res += i*cnt+n/i;

    }

    return res;

}

int32_t main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    int t; cin >> t;

    while(t--){

        int n;  cin >> n;

        cout<<H(n)<<"\n";      

    }

}