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로 표현 할 수 있다.

 

	#include<iostream>
	#include<cmath>
	using namespace std;
	const int MAX_N = 10000000;
	// index의 가장 작은 소인수
	int minFactor[MAX_N + 1];
	// index를 소인수 분해 했을때, minFactor[index]가 몇 승 포함되었는지
	int minFactorPower[MAX_N + 1];
	// index의 약수 갯수
	int factor[MAX_N];
	int n;
	// 에라토스테네스의 체를 이용해서 minFactor저장
	void eratosthenes2() {
	minFactor[0] = minFactor[1] = -1;
	int sqrtn = (int)(sqrt(MAX_N));
	for (int i = 2; i <= MAX_N; i++)
	minFactor[i] = i;
	// n의 소인수는 항상 sqrt(n)이하이다
	for (int i = 2; i <= sqrtn; i++) {
	if (minFactor[i] == i) {
	for (int j = i * i; j <= MAX_N; j += i)
	if (minFactor[j] == j)
	minFactor[j] = i;
	}
	}
	}
	void getFactorsSmart() {
	factor[1] = 1;
	for (int i = 2; i <= MAX_N; i++) {
	// i가 소수일 경우
	if (minFactor[i] == i) {
	minFactorPower[i] = 1;
	factor[i] = 2;
	}
	// i가 소수가 아닐경우
	else {
	int p = minFactor[i];
	int m = i / p;
	// i에서 p의 승수가 1일때
	if (p != minFactor[m])
	minFactorPower[i] = 1;
	// i에서 p의 승수가 2이상일때
	else
	minFactorPower[i] = minFactorPower[m] + 1;
	int a = minFactorPower[i];
	factor[i] = factor[m] * (a + 1) / a;
	}
	}
	}
	int main() {
	int testcase;
	cin >> testcase;
	eratosthenes2();
	getFactorsSmart();
	while (testcase--) {
	int lo, hi, result = 0;
	cin >> n >> lo >> hi;
	for (int i = lo; i <= hi; i++)
	if (factor[i] == n)
	result++;
	cout << result << endl;
	}
	}

view raw algospot 비밀번호 486 (문제 ID: PASS486).cpp hosted with ❤ by GitHub

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

GitHub - sbl133/JongmanBook

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

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