# AtCoder doubt

Could someone tell me intuition behind this solution
https://atcoder.jp/contests/abc172/submissions/14736523

how this function is calculating the things

  ll c2(ll x) {
return x * (x - 1) / 2;
}


https://codeforces.com/blog/entry/79438

1 Like

n/i is the number of numbers I divides
And ans adds up (n/i)*(n/i+1)/2 .
By the property mentioned in question.
Also, sieve method will give you ac.

I got AC by sieve , but unable to understand this thing…
I know (n/i) are the total numbers which i divides . . but i * nC2(n/i) ? is answer , How ?

Unrelated solution: Just take advantage of the time limit- 3 sec.

ll x=0;
for(ll i=1;i<=n;i++){
for(ll j=i;j<=n;j+=i){
x+=j;
}
}
cout<<x;

Each step u have i* (cou +1)C2
It is actually( i + 2i + 3i +4 i …+(n/i))*i.
As they are asking if x is a divisor of k it contributes k to the sum. so since i is a divisor of i,2i,3i,4i…
So u get ‘i’ multiplied by(summation 1 to (n/i))
Hope you got this now.

1 Like

Below code in 2(Root(N))

    import sys

def S(k):
return k * (k + 1) // 2

M = int((N+1)**.5)
ans = 0
# 蜑榊濠
for i in range(1, N // (M+1) + 1):
ans += i * S(N // i)
# 蠕悟濠
for k in range(1, M+1):
ans += S(k) * (S(N//k) - S(N//(k+1)))
print(ans)


and how this works ?

@galencolin explain O(N) and above code both please

1 Like

Can you share your answer ? I Wanna see how’s you used sieve.

my AC in-contest submission

Please let me know if you find Explanation for O(sqrt(n)) solution.

O(n) solution is here. Understand that first, because the O(\sqrt{n}) is just a sped-up version.

The main idea is that the answer is equal to \sum\limits_{i = 1}^{n}{i \cdot s(\lfloor \frac{n}{i} \rfloor)}, where s(n) is the sum of numbers from 1 to n: \frac{n(n + 1)}{2}. But there are only O(\sqrt{n}) distinct values of \lfloor \frac{n}{i} \rfloor, so you can group them together and compute the entire answer for a value of \lfloor \frac{n}{i} \rfloor with O(1) formulas. See here

1 Like

Another problem which uses similar concept: 616E

1 Like

This was a great problem… I did it with DnC tho, the math was too hard for me
I think I should look at it again…

@hetp111 Try this one also: SUMPRO

1 Like