AtCoder doubt

help
#1

Here’s the problem https://atcoder.jp/contests/abc172/tasks/abc172_d

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

how this function is calculating the things

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

https://codeforces.com/blog/entry/79438
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