PASS486

알고스팟 PASS486

1. eratosthenes함수를 통해 minFactor를 각각 저장을 해준다.

2. getFactors함수를 통해 약수의 개수를 구한다.
 2-1. 소수일 경우 factor = 2, minFactorPower = 1이 된다. ex) 7 = 7^1
 2-2. 소수가 아닐 경우 minFactor로 나눈 값을 m에 저장
       만약 m의 minFactor와  p가 다르면 n의 minFactorPower는 1이 된다.
       (만약 n이 6일 때 6 = 2 * 3 인데 p = 2가 되며 m = 3이된며, 여기서 p != minFactor[m]
        이란 말은 2라는 숫자가 6은 하나밖에 가지고 있지 않다는 뜻인다. 따라서
        minFactorPower[6] = 1되는 것이다.)
        하지만 같다면 minFactorPower[m] +1 을 해준다.

67,500의 소인수 분해는
67500 = 2^2 * 3^3 * 5^4 이다.
minFactor인 2로 나누었을 때 33750 = 2 * 3^3 * 5^4이 나오는데 33750의 약수의 개수는
(1 + 1) * (3 + 1) * (4 + 1)이다. 즉, 67500은 33750약수에 개수에서 2를 나눈 뒤 3을 곱하면
되는 것이다 따라서 (factors[n]/a) *(a+1)이란 식이 나오는 것이다.

[-] Collapse

#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;
}