Discussion @ 1118. Nontrivial Numbers @ Timus Online Judge

Hint

Posted by Takanashi Rikka 26 Feb 2016 09:12

Calculates sum of divisors.
O(lim * log(lim)).
for(int i = 2; i <= lim; ++i){
    ++s[i];
    for(int j = i + i; j <= lim; j += i)
        s[j] += i;
}

Re: Hint

Posted by Pussy Hunter 16 Jul 2016 03:07

Maybe I don't understand it clear, but I think it will get TL.
Difficult of this algorithm = O(n^2)

Re: Hint

Posted by Noob 17 Jul 2016 18:10

No, it's O(n log n). Learn some math.

Re: Hint

Posted by Egor 20 Nov 2016 01:52

https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

Discussion of Problem 1118. Nontrivial Numbers