PASS486 (중, p. 501)

문제#

어떻게 풀었나?#

책을 보고 풀진 않았지만, 이 문제를 풀기 전에 책에 나온 에라토스테네스의 체와 빠른 소인수 분해 에 나온 내용을 읽었어서 난이도 ‘하’ 수준으로 문제를 풀 수 있었다.

어떤 수의 약수의 개수는 소인수 분해 한 결과만 있으면 빠르게 구할 수 있다. 어떤 값이 $x^a \times y^b \times r^c$으로 소인수분해 된다면( $x,y,r$은 소수), 약수의 개수는 $(a+1)(b+1)(c+1)$이 된다.

따라서 에라스토스테네스의 체로 숫자별 최소 소수를 딱 한번 구한 뒤, 빠른 소인수 분해로 약수의 개수를 찾으면 된다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
#define N 10000000
int mn_prime[N+1];
void Eratosthenes() {
    for(int i=0; i<=N; i++) mn_prime[i] = i;
    int sqrtn = (int)(sqrt(N));
    for(int i=2; i<=sqrtn; i++) {
        if (mn_prime[i] == i) {
            for (int j = i * i; j <= N; j += i) {
                if (mn_prime[j] == j) mn_prime[j] = i;
            }
        }
    }
}
int PrimeFactorCnt(int x) {
    int ans=1, cnt=0;
    int prv_prime = -1;
    while(x>1) {
        if(prv_prime != mn_prime[x]) {
            ans*=(cnt+1);
            cnt=1;
        }
        else cnt++;
        prv_prime = mn_prime[x];
        x/=mn_prime[x];
    }
    if(cnt>0) ans*=(cnt+1);
    return ans;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    Eratosthenes();
    while(tc--) {
        int n,lo,hi;
        cin >> n >> lo >> hi;
        int ans=0;
        for(int i=lo; i<=hi; i++) {
            if(PrimeFactorCnt(i) == n) ans++;
        }
        printf("%d\n", ans);
        
    }
    return 0;
}

Comment#

빠른 소인수분해 방법이 상당히 인상적이었다.