반응형 약수1 #1457 정확해 정확해라는 문제는 약수들의 합을 구하는 문제입니다. 난이도는 Gold I 문제이긴 하지만, 이게 수학적인 이해를 하지 못 하면 조금 어렵습니다. 그래서인지 정답자가 제가 푼 시점에서는 40명에 그칩니다. 약수의 개수를 구하는 문제는 꽤 어렵습니다. \[ \sigma_0(n) = n( \lbrace x | n~ mod~ x = 0 \rbrace ) \] 으로 약수를 구하는 식을 사용한다면, \(\sqrt{n}\)에 해당하는 만큼 약수가 되는 개수를 구하던지, 소인수 분해를 해주어야 합니다. 그런데 만약 1 부터 n까지의 약수들의 개수의 합을 구하라는 문제라면 어떨까요? \[ S(n) = \sum_{k=1}^{n} \sigma_0(k) \] 하나의 수의 약수의 개수를 구하는 것도 어려운데, 일정 숫자 범위의.. 2022. 8. 16. 이전 1 다음 728x90