조화 급수 : ps에서 간간히 나온다.
A(x)을 x의 약수 갯수라고 해 봅시다. 이 때, A(1) + ... + A(n)의 값은 어디에 근접할까요? 이 간단한 질문에서, 오늘의 주제를 이야기 해 보도록 하겠습니다. a가 b의 배수라면, b는 a의 약수입니다. 이 점을 이용해 봅시다. 예를 들어 4의 약수는 1, 2, 4입니다. 그러면, 4는 1의 배수이면서 2의 배수이고, 4의 배수이기도 합니다. 그러면 1에서 출발해서, 1만큼 건너 뛸 때, 2에서부터 출발해서 2만큼 건너 뛰었을 때, 4에서부터 출발해서 4만큼 건너 뛰었을 때, 4를 visit 할 수 있게 됩니다. 그러면 1부터 n까지의 약수의 갯수의 합을 구하는 건 어떻게 하면 좋을까요? 역시 거꾸로 생각하시면 됩니다. 예를 들어서, 약수가 1인 수들을 찾는다고 해 봅시다. 그러면 1,..
자료알고/알고리즘
2019. 9. 5. 18:05
최근댓글