AtCoder doubt

help
1

Here’s the problem D - Sum of Divisors

Could someone tell me intuition behind this solution
:point_right: Submission #14736523 - AtCoder Beginner Contest 172

how this function is calculating the things

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

Read the explanation here.

1 Like
3

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.

4

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 ?

5

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;
6

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
7

Below code in 2(Root(N))

    import sys
    readline = sys.stdin.buffer.readline
     
    def S(k):
        return k * (k + 1) // 2
     
    N = int(readline())
    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 :slight_smile:

1 Like
8

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

9

my AC in-contest submission

10

Thanks for the link really helpful.

11

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

12

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
13

Another problem which uses similar concept: 616E

1 Like
14

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

15

@hetp111 Try this one also: SUMPRO

1 Like