사용자 도구

사이트 도구


ps:problems:boj:15106

Fear Factoring

ps
링크https://www.acmicpc.net/problem/15106
출처BOJ
문제 번호15106
문제명Fear Factoring
레벨플래티넘 4
분류

정수론

시간복잡도O(sqrt(n))
인풋사이즈n<=10^12
사용한 언어Python
제출기록29200KB / 2140ms
최고기록1140ms
해결날짜2021/06/10

풀이

  • σ(x)은 x의 약수의 합을 의미하는 함수이다. f(1)+f(2)+...+f(N)을 계산에 설명했듯이 σ(1)+σ(2)+…+σ(x)는 O(sqrt(x))에 계산이 가능하다.
  • σ(a)+σ(a+1)+…+σ(b) 는 {σ(1)+σ(2)+…+σ(b)} - {σ(1)+σ(2)+…+σ(a-1)} 으로 바꿔 계산하면 O(sqrt(b))에 계산 가능하다.

코드

"""Solution code for "BOJ 15106. Fear Factoring".

- Problem link: https://www.acmicpc.net/problem/15106
- Solution link: http://www.teferi.net/ps/problems/boj/15106
"""


def sigma_sum(n):
    sigma_sum = 0
    i = 1
    while i <= n:
        j = n // (n // i)
        sigma_sum += n // i * (j - i + 1) * (j + i) // 2
        i = j + 1
    return sigma_sum


def main():
    a, b = [int(x) for x in input().split()]
    print(sigma_sum(b) - sigma_sum(a - 1))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
X U W F P
 
ps/problems/boj/15106.txt · 마지막으로 수정됨: 2021/06/10 14:39 저자 teferi