algospot PASS486

문제 링크입니다: https://algospot.com/judge/problem/read/PASS486

완전탐색법과 에라토스테네스의 체, 총 두가지 방법으로 풀어봤습니다.

완전탐색법은 http://jaimemin.tistory.com/440?category=988050와 비슷하게 풀었습니다.

'만취한 상범' 문제에서는 한번 지나갈 때마다 문을 여닫았지만 이 문제에서는 약수의 갯수를 추가했습니다.

에라토스테네스의 체를 이용한 방법은 소인수분해했을 때 약수의 갯수 = Π(i번째 지수+1) 공식을 이용하여 풀었습니다.

예를 들자면 100= 2^2 * 5^2입니다. 따라서 약수의 갯수는 3 * 3 = 9 입니다.

100의 최소 약수인 2를 나누면 50 = 2 * 5^2 이므로 약수의 갯수는 2 * 3 = 6 입니다.

100의 약수의 갯수를 모른다고 가정하고 50의 약수 갯수는 6인걸 알고 있다면 3/2를 곱해 100의 약수의 갯수가 9임을 알 수 있습니다.(2의 지수가 1에서 2로 변했으므로 (2+1)/(1+1))

#include <iostream>

#include <cmath>

#include <cstring> //memset

using namespace std;

 

const int MAX = 10000000; //천만

 

//minFactor[i] -> i의 가장 작은 소인수(i가 소수인 경우 자기 자신)

int minFactor[MAX + 1];

//minFactorPower[i] -> i의 소인수 분해에는 minfactor[i]의 몇 승이 포함되어있는가

int minFactorPower[MAX + 1];

//factors[i] -> i가 가진 약수의 수

int factors[MAX + 1];

 

void erastothenes(void)

{

        //1은 항상 예외 처리

        minFactor[0] = minFactor[1] = -1;

        //모든 숫자를 처음에는 소수로 표시

        for (int i = 2; i <= MAX; i++)

               minFactor[i] = i;

        //에라토스테네스의 체를 수행

        int sqrtN = int(sqrt(MAX)); //루트 N

        for (int i = 2; i <= sqrtN; i++)

               if (minFactor[i] == i)

                       for (int j = i*i; j <= MAX; j += i)

                              //아직 약수를 본적 없는 숫자인 경우 i를 써 둔다

                              if (minFactor[j] == j)

                                      minFactor[j] = i;

}

 

void getFactorsSmart(void)

{

        factors[1] = 1;

        for (int num = 2; num <= MAX; num++)

        {

               //소수인 경우 약수가 두개 뿐

               if (minFactor[num] == num)

               {

                       minFactorPower[num] = 1; //1승

                       factors[num] = 2; //약수 두개

               }

               //소수가 아닌 경우, 가장 작은 소인수로 나눈 수의

               //약수의 수를 응용해 num의 약수의 수를 찾는다

               else

               {

                       int prime = minFactor[num];

                       int divisor = num / prime;

                       //divisor가 prime으로 더이상 나누어지지 않는다면

                       if (prime != minFactor[divisor])

                              minFactorPower[num] = 1;

                       else

                              minFactorPower[num] = minFactorPower[divisor] + 1;

                       int exponent = minFactorPower[num];

                       factors[num] = (factors[divisor] / exponent)*(exponent + 1);

               }

        }

}

 

//완전탐색법

void getFactorsBruteForce(void)

{

        memset(factors, 0, sizeof(factors));

        for (int div = 1; div <= MAX; div++)

               for (int multiple = div; multiple <= MAX; multiple += div)

                       factors[multiple]++;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

 

        erastothenes();

        getFactorsSmart();

        //getFactorsBruteForce();

        for (int i = 0; i < test_case; i++)

        {

               int divisorNum, low, high;

               cin >> divisorNum >> low >> high; //약수 갯수, 범위

               if(divisorNum > 400 || low<1 || low>MAX || high<1 || high>MAX)

                       exit(-1);

 

               int result = 0;

               for (int j = low; j <= high; j++)

                       if (factors[j] == divisorNum)

                              result++;

               cout << result << endl;

        }

        return 0;

}

[에라토스테네스의 체 이용]

[완전탐색법 이용]

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략