ABC172D

https://gyazo.com/d184857cee408b25e6ea65eb0d7f3799

Multiplication is a repetition of addition, and addition does not change the result when the order is changed.

Counting the number of items that satisfy the condition" is also a process that takes the sum of "1 if the condition is satisfied and 0 if it is not satisfied.

So "K times K after counting" can be interchanged in order to "K, if the conditions are met, add up".

https://gyazo.com/c5ad2bfbd34a616a96d2e65e5a7c4177

https://gyazo.com/0d96d3c6ed540a523a4c41b8aff945c6

This is the way it's presented in the commentary

code:python

def solve(N):

ret = 0

for i in range(1, N + 1):

num = N // i

end = num * i

ret += (i + end) * num // 2

print(ret)

I will explore this issue later, as I have heard that there are two ways to do this, one with a smaller order and the other with a larger order but still manageable to get through.

By the way, this method of adding vertically adds one loop at a time, even though there is only one from halfway down anyway. If we add diagonally, we only need half a loop. However, if you are going to add diagonally...

https://gyazo.com/8ce00ba56e9147b6791e01a708f97b66

Add diagonally to the top left corner tightly. Then the number of loops would be on the order of the root n.

https://gyazo.com/eefa326a4a1e00751adbecea14d340fd

code:python

def solve(N):

ret = 0

i = 2

while True:

step = i // 2

start = (i + 1) // 2 * step

if start > N:

break

end = N // step * step

ret += (start + end) * ((end - start) // step + 1) // 2

i += 1

print(ret)

50 times faster.

---