PASS486

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

algospot.com :: PASS486

1. DP를 활용하여 소수값을 배열에 저장하는 방법으로 해결할 수 있음

2. 그렇지 않다면 TIME_OVER 에러 발생이 큼

 

#include<iostream>
#include<cmath>
using namespace std;
#define MAX_N 10000001
int minFactor[MAX_N];
int minFactorPower[MAX_N];
int factors[MAX_N];
void eratosthenes() {
    minFactor[0] = minFactor[1] = -1;
    for (int i = 2; i <= MAX_N; ++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_N; j += i){
                if (minFactor[j] == j)
                    minFactor[j] = i;
            }
        }
    }
}
void getFactors() {
    factors[1] = 1;
    for (int n = 2; n <= MAX_N; ++n){
        if (minFactor[n] == n) {
            minFactorPower[n] = 1;
            factors[n] = 2;
        }
        else {
            int p = minFactor[n];
            int m = n / p;
            if (p != minFactor[m])
                minFactorPower[n] = 1;
            else
                minFactorPower[n] = minFactorPower[m] + 1;
            int a = minFactorPower[n];
            factors[n] = (factors[m] / a) * (a + 1);
        }
    }
}
int main(){
    int t; cin >> t;
    eratosthenes();
    getFactors();
    while (t--){
        int n, lo, hi; cin >> n >> lo >> hi;
        int ans = 0;
        for (int i = lo; i <= hi; i++)
            if (factors[i] == n) ans++;
        cout << ans << endl;
    }
    return 0;
}