BOJ 9359번 서로소

BOJ 9359번 : 서로소

1 <= A <= B <= 10^15

1 <= N <= 10^9

[A, B] 구간에 존재하는 수들 중 N와 서로소인 수들의 수를 구하는 문제이다.

N을 소인수 분해 해보자. 2^a * 3^b * 5^c * 7^d * 11^e + ... 의 형태가 나올 것이다.

[A, B] 구간의 수들중 N의 어떤 소인수의 배수도 아닌 수들은 N과 서로소일 것이다.

반대로 N의 어떤 소인수의 배수라면 N과 서로소가 아닐 것이다.

그럼 N과 서로소인 수를 세는 대신 N과 서로소가 아닌 수를 세서 [A, B] 구간에 있는 수의 수인 B - A + 1에서 뺴면

답을 구할 수가 있을 것이다. 그럼 [A, B] 에서 N과 서로소가 아닌 수는 어떻게 셀까?

위에서 말했듯이 N의 소인수들의 배수인 수들을 세면된다. 그럼 일단 N을 소인수 분해 한뒤 

각각의 소인수들에 대해 [A, B] 에 존재하는 배수들의 수를 단순히 나눗셈으로 구해서 더하면 끝일까?

아니다. 왜냐하면 각각의 소인수들의 공배수들은 여러번 세기 때문이다.

그럼 수를 인덱스로 하는 배열이나 map 같은 자료구조를 사용하여 1을 대입하는식으로 표시해주고

마지막에 1인 수들을 세는 식으로 하면 되지않나 라고 생각하는 것도 잠시 그렇게하면 최악의 경우

적어도 O(B) 는 걸릴 것이다. 그럼 어떻게 하면될까?

이 문제의 키는 포함 배제의 원리이다.

결국 우리가 구하고 싶은 것은 N의 각각의 소인수들의 배수들의 합집합이기 때문에 간단하게 포함배제의 원리로 풀 수가 있다.

풀이의 큰 틀은 이렇게 되는데 우리에게 남은 숙제는

소인수 분해는 어떻게하느냐이다.

과연 최악의경우 10^9 인 N을 소인수 분해하는것이 가능할까?

무식하게 생각해 보면 O(N) 이 걸린다는 것을 알 수가 있다.

왜냐하면 더이상 나누어 지지 않을 때까지 1~N 까지의 수들을 탐색하며 N를 나눌수 있는 수로

N을 나누는 과정이 필요하기 때문이다. 하지만 과연 N개 수를 모두 확인을 할 필요가 있을까?

아니다. 우선 한가지 알아야 할 사실이 있다. 자연수에서 소수가 아닌수에 비해 소수의 수는 극히 적다는 사실이다.

그렇기 때문에 10억 이하의 자연수들 중에 소수의 수는 얼마 되지않는다.

즉, 최악의 경우에도 10억 이하인 소수들만 검사하면서 N을 나눠주면 소인수 분해가 가능하다.

그럼 10억 이하인 소수들을 구해야하는데 우리들은 소수 판별을 할 때 흔히 에라토스테네스의 체를 사용한다.

에라토스테네스의 체의 시간 복잡도는 O(nlglgn) 이며 O(n) 의 공간복잡도는 필수이다.

그런데 N은 최대 10억이기 때문에 10억 이하의 소수를 모두 구하기는 힘들다는 것을 깨닫게된다....

그럼이제 어떻게 할까...

잘 생각해보면 N 의 가장 큰 소인수는 root(N) 보다 클 수가 있지만, 두번째로 큰 소인수가 root(N) 보다

클 수는 없다는 것을 알 수가있다. 그렇기 때문에 우선 root(N) 보다 작거나 같은 소인수들을 다 구하고나서

지금 까지 구한 소인수들의 곱으로 N을 나눈 값이 1이 아니라 다른 어떤 수라면

그 수는 무조건 root(N) 보다 큰 N의 소인수 이다.

즉, 우리는 root(N) 이하의 소수들만 알고있으면 되고, 이 소수들로만 소인수 분해를 하고 남은 수가 1이 아니라면

그 수만 하나 더 추가해주면 소인수 분해가 완료된다.

그리고 추가적인 두가지 팁은

개인적으로는 소인수 분해를 할 때 map 을 사용하면 편하고,

포함 배제의 원리는 사용할 때 bitmask 를 사용하면 엄청 편하다는것이다.

어차피 N <= 10^9 인, N의 소인수들의 수는 얼마 되지 않으므로 그 수들을 각각의 비트로 보고

비트가 켜져있으면 그 수도 공배수에 포함되는것이고, 아니면 포함되지 않는것으로 보아

켜진 수들의 공배수인 수들을 보겠다는 식으로 하면 된다.

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
#include <cassert>
 
using namespace std;
 
typedef long long ll;
 
ll A,B,N;
int notPrime[100003];
vector<int> primes;
map<ll, int> mp;
vector<ll> divisors;
 
int main(){
    int T;
    cin >> T;
 
    for(int i = 2; i <= 100000; i++){
        if(notPrime[i]) continue;
        for(int j = 2*i; j <= 100000; j+=i){
            notPrime[j] = 1;
        }
    }
 
    for(int i = 2; i <= 100000; i++){
        if(!notPrime[i]) primes.push_back(i);
    }
    for(int t = 1; t <= T; t++){
        cin >> A >> B >> N;
        divisors.clear();
        mp.clear();
 
        while(N > 1){
            bool divided = false;
            for(auto p : primes){
                if(N % p == 0) {
                    N /= p; 
                    mp[p] = 1;
                    divided = true;
                    break;
                }
            }
            if(!divided) break;
        }
 
        if(N != 1) mp[N] = 1;
 
        for(auto it = mp.begin(); it != mp.end(); it++){
            divisors.push_back((*it).first);
        }
 
        int size = divisors.size();
        ll ans = 0;
        for(int i = 0 ; i < 1<<size ; i++){
            if(!i) continue;
            int cnt = 0;
            ll div = 1;
            for(int j = 0 ; j < size; j++){
                if(i&(1<<j)) div *= divisors[j], cnt++;
            }
            ll lo = (A+div-1)/div*div;
            ll hi = B/div*div;
            if(lo>hi) continue;
            ll gasu = (hi-lo)/div + 1;
            ans += cnt%2 ? gasu : -gasu;
        }
        cout << "Case #" << t << ": " <<  B - A + 1 - ans << endl;
    }
    return 0;
}