BaaaaaaaarkingDog
코딩, 해킹
[BOJ] 11152번: Inverse Divisor

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


약수의 합이 N이 되는 수에 p라는 소인수가 포함되어 있을 경우 N은 $1+p$,$1+p+p^2$, $1+p+p^2+p^3$...  중 어느 하나로 나누어져야한다는 사실을 이용해 recursive하게 식을 돌립니다. p가 $\sqrt(N)$ 이상이면 p는 많아봐야 1개가 있을 수 밖에 없으므로 $\sqrt(N)\$ 까지만 미리 소수를 구해두고 이후에는 remain 값에서 1을 뺀 것이 소수인지를 확인해나가면 됩니다. 뭔가 CTF로 출제하고 싶게 생겼네요.


https://github.com/blisstoner/BOJ/blob/master/11152.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 5615번: 아파트 임대  (0) 2018.09.20
[BOJ] 13891번: Find C  (0) 2018.09.19
[BOJ] 2990번: BAZA  (0) 2018.09.19
[BOJ] 11152번: Inverse Divisor  (0) 2018.09.19
[BOJ] 1044번: 팀 선발  (2) 2018.09.16
[BOJ] 16120번: PPAP  (0) 2018.09.15
[BOJ] 16139번: 인간-컴퓨터 상호작용  (0) 2018.09.15
  Comments
댓글 쓰기