[백준] 17425번: 약수의 합

https://www.acmicpc.net/problem/17425

initial

So i tried finding the pattern cuz this was gold 4 question and the obvious easy way of checking and counting each factor 1 by 1 is bound to have runtime issues. I thought maybe this was a dp question cuz as you seen in the image, dp[2]=3, dp[4]=7, dp[8]=15, dp[16]=31 so it increments like 4,8,16. But same pattern for dp[3],dp[9],dp[27]. But what about dp[6] and its multiples? I cant find pattern for that

So i googled cuz and we can use sieve of erathoses + DP! Instead of trying to find a DP pattern, we can see that for any multiple of a number, it is bound to have that number as its factor. So since we want to find the sum of factors of a number, we can accumulate the factors along the way. Lets take number 2 for example. For all multiples of 2 like 4,6,8,10,etc, those numbers have 2 as its factors. So we are gonna store 2 in our storage list (by incrementing 2 at that index of that multiple).

So we are gonna have 1 dp list and 1 storage list. Once we finish storing each factor in that factors’ multiple’s index in that storage list, we compute the current index’s dp value. DP value stores the accumulated sum of factors up to index n so it needs to add previous state (dp[n-1]) AND the sum of factors in that index in that storage list (storage_list[n]).

solution

import sys
input = sys.stdin.readline

t = int(input())

def sieve():
    dp = [0 for _ in range(1000001)]
    tmp = [0 for _ in range(1000001)]
    for i in range(1, 1000001):
        # tmp[i] += i
        for multiple in range(i , 1000001,i):
            tmp[multiple] += i
        dp[i] = dp[i - 1] + tmp[i]
    return dp

dp = sieve()
for _ in range(t):
    val = int(input())
    print(dp[val])

revisited july 30th 24

so it is dp[i]=dp[i-1]+dp[i-2]+...dp[0]. I got that we needed another storage list to store these divisors but i couldnt think of logic to increment the sum by having a double for loop. The inner for loop increments with steps of i until 1 mil+1 to "add" i (divisor) to the tmp list, which stores the sum of all divisors of value i. Then after that is done, we update dp[i] value with dp[i-1]+tmp[i].

complexity

time is t n log n

log n cuz the multiple calculation increments with step of i

The time complexity of the given code is O(T N log(N)), where T is the number of test cases and N is the upper limit for which we are precomputing the sum of divisors. This is because for each test case, we iterate over all numbers from 1 to N to compute the sum of divisors, and for each number, we iterate over its multiples up to N.

The space complexity is O(N), as we are storing the sum of divisors for each number up to N in the dp array.