algospot 비밀번호 486 (문제 ID: PASS486) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/PASS486

algospot.com :: PASS486

[lo, hi] 범위 정수중에 n개의 약수를 가지는 정수의 갯수를 구하는 문제이다.

먼저 에라토스테네스의 체를 이용하여 해당 정수(index)가 가지는 소인수의 최솟값을 저장하는 배열(minFactor)을 만든다.

minFactor를 이용하면 해당 정수(index)를 소인수분해 했을때 제일작은 소인수가 몇승인지를 저장하는 배열(minFactorPower)와 해당 정수(index)가 가지는 약수의 갯수를 저장하는 배열(factor)를 생성할 수 있다.

factor는 해당 정수(index)의 가장 작은 소인수가 p이고, 이 소인수가 a번 출현 한다면(index를 소인수 분해 했을때 p의 지수가 a이면) factor[n] = factor[n/p] * (a+1)/a로 표현 할 수 있다.

 

코드원본: https://github.com/sbl133/JongmanBook/blob/main/14.%20NumberTheory/PASS486.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1