본문 바로가기

Programming Problems/Number theory

N 보다 작으면서 3 또는 5의 배수인 숫자들의 합 구하기

처음에는 3또는 5만 소인수로 갖는 것들의 합 구하기로 생각해서, 3의 거듭제곱 중 가장 작으면서 큰거 i, 5의 거듭제곱 중 가장 작으면서 큰거 j 라고 하면

(i,j) 2중 for 루프의 모든 숫자들 중 N 보다 작은 것들을 전부 더해나갈 생각이었다. 갯수는 log^2N 이고 각각에 대해 합을 구하는건 단계별로 3씩 곱해나가는 셈이니까 1이 걸려서 총 시간 복잡도는 O(log^2N) 쯤 되겠다.


---


근데 이 문제는 "3 또는 5의 배수" 이기 때문에..


10 이면


3 6 9 = 18

5 = 5

tot : 23


매우 자명하게 

3 total = N/3 * (N/3*(N/3+1)/2)

5 total = same but 5

그리고 이 둘의 합을 하면 중간에 15의 배수가 겹치므로

15 total = same but 15


결과적으로 3과 5의 배수는

total = 3total + 5total - 15total 이다.


O(1) 알골이 되는 셈..