14.3_비밀번호486_PASS486

문제 설명

algospot.com :: PASS486

• n개의 약수를 갖는 숫자 X를 비밀번호로 선택한다.(n < 400)
• 비밀번호는 lo~hi 범위 내의 숫자이다(양 끝의 수 포함)(1 <= lo <= hi <= 10,000,000)

=> lo ~ hi 범위 이내에 정확히 n개의 약수를 갖는 숫자의 개수를 출력하기

 

문제 풀이

약수의 개수 미리 구해두기

이 문제는 어떤 한 수가 가지는 약수의 개수를 구해야 한다.

그렇기 때문에 약수 개수를 미리 배열에 구해두고, 나중에 사용하면 한 숫자에 대해 두 번 계산하는 경우를 방지할 수 있다.

a가 b의 약수라는 것은 곧 b는 a의 배수라는 뜻이다.

그러므로 a의 배수인 모든 수에 약수의 개수를 +1 해주고, a+1의 배수, a+2의 배수, ... 를 거쳐가면서 약수의 개수를 전부 계산하면, 1 ~ 10,000,000의 모든 약수의 개수를 구할 수 있다.

 

그 후 lo와 hi사이에 포함되는 수 중 n개의 약수를 가진 숫자의 개수를 셌다.

 

문제 풀이 코드

#include <iostream>

#define MAXVALUE 10000000

using namespace std;

int divisorCnt[MAXVALUE + 1];	// 약수 개수 저장

void calDivisorCnt() {	// 약수 배열 만들기
	for (int i = 2; i <= MAXVALUE; ++i) {
		for (int j = i; j <= MAXVALUE; j += i) {
			++divisorCnt[j];
		}
	}
}

int main() {
	fill_n(divisorCnt, MAXVALUE + 1, 1);
	calDivisorCnt();
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		int n, lo, hi;
		int ans = 0;
		cin >> n >> lo >> hi;
		for (int i = lo; i <= hi; ++i) {
			if (divisorCnt[i] == n)
				++ans;
		}
		cout << ans << endl;
	}
	return 0;
}