algospot PASS486

algospot : https://algospot.com/judge/problem/read/PASS486

github : https://github.com/junho0956/Algorithm/blob/master/algospot%20PASS486/algospot%20PASS486/%EC%86%8C%EC%8A%A4.cpp

 

** 시간제한 5000ms, 메모리제한 128MB **

 

이 문제를 푸는데에는 3가지 방법이 있습니다.

 

첫번째 방법

모든 수를 각각 약수를 다 구한다.

임의의 수 N 이 있을 때 1부터 sqrt(N)까지의 모든 수를 N에 mod 해보는 방법입니다.

이에 대해 각 수 당 시간복잡도는 sqrt(N)이 필요하고, 

첫번째 방법을 이용해서 구현을 해보지는 않았는데 수의 범위가 최대 1000만이니

1000만*sqrt(N) 은 주어진 시간이 5초라서.. 사실 통과할것 같기는 합니다.

하지만 보통 이렇게 큰 시간을 허용해주지 않으니 다음 방법을 확인해보겠습니다.

 

두번째 방법

소수 알고리즘인 에라토스테네스의 체를 이용해서

각 수의 최소약수를 미리 구해놓으면 소인수분해를 빠르게 할 수 있고,

소인수분해를 이용해서 약수의 갯수를 빠르게 알 수 있습니다.

저는 이 방법을 통해서 800ms 로 해결했습니다.

종만북을 통해서 에라토스테네스의 체로 소인수분해를 할 수 있는 방법을 처음알았는데

감탄하고 갑니다..

 

세번째 방법은 완전히 소인수분해 하지 않고도 약수의 수를 셀 수 있는 방법인데,

두번째 방법보다 더욱 빠르다고 합니다.

아직 이해를 못해서 좀더 공부하고 차후 수정하겠습니다.

 

아래는 두번째 방법으로

에라토스테네스의체 -> 소인수분해 -> 약수의 갯수 찾는 순서로 구현되어 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
using namespace std;
const int MAXNUM = 1e7 + 1;
 
int minFactor[MAXNUM];
int numFactor[MAXNUM];
 
void Factor() {
    for (int i = 0; i < MAXNUM; i++) minFactor[i] = i;
    for (int i = 2; i <= sqrt(MAXNUM); i++) {
        if (minFactor[i] == i) {
            for (int k = i * i; k < MAXNUM; k += i) {
                if (minFactor[k] == k) minFactor[k] = i;
            }
        }
    }
 
    for (int i = 2; i < MAXNUM; i++) {
        int n = i;
        int ans = 1;
        int cnt = 0;
        int num = minFactor[i];
        while (n > 1) {
            if (minFactor[n] == num) cnt++;
            else {
                ans *= (cnt + 1);
                cnt = 1;
                num = minFactor[n];
            }
            n /= minFactor[n];
        }
        ans *= (cnt + 1);
        numFactor[i] = ans;
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    Factor();
 
    int T; cin >> T;
    while (T--) {
        int n, lo, hi;
        cin >> n >> lo >> hi;
        int answer = 0;
        for (int i = lo; i <= hi; i++) {
            if (numFactor[i] == n) answer++;
        }
        cout << answer << "\n";
    }
 
    return 0;
}