ps:problems:boj:15106
목차
Fear Factoring
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | 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()
ps/problems/boj/15106.txt · 마지막으로 수정됨: 2021/06/10 14:39 저자 teferi
토론