[BOJ-9359]서로소

하........

처음에 개꼬였다. 

아예 문제도 잘못읽고, 문제로 잘못이해하고................

슈바............ 결론은...... 

처음에 잘못된 접근부터 시작하자면, 

A B X 라는 숫자를 받고나서 생각을 했다. A부터 B까지 있는 수 중에? X와 서로소인 것은? 그러면 당연하게 아니 당연한건아닌데 무슨 생각인건지 그때 당시 코드작성할 때는 당연하다고 생각한 ㅄ..... B/X - (A-1)/X 하면 답이네? ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ이랬다ㅋㅋㅋㅋㅋㅋㅋㅋ 

그렇게 코드를 한 5번틀리고서 """ 완전 바보넼ㅋㅋㅋㅋㅋㅋ """ 하고 이제 제대로 이해하고나서 보니 """ 포함배제원리 """ 를 어떻게 써야할까 생각을 하게 되었다. 음... 뭐 DFS 재귀적으로 함수를 호출해서 계산을 하고 ret 값을 더하고 이 순서를 반복해서 하는 건데 

일단 

포함배제의 원리 - 위키백과, 우리 모두의 백과사전

집합이 세 개일 때의 포함배제의 원리를 벤 다이어그램 으로 표현한 것 조합론 에서, 포함배제의 원리 (包含排除의原理, 영어 : inclusion–exclus...

ko.wikipedia.org

이거 먼저 보고나서 코드를 짜면 된다. 근데 A B 로 주어지는 수가 1e+15, 

X로 주어지는 수의 최대가 1e+9 (10억) 이기 때문에 소인수를 어떻게 구할까? 라고 생각을 해봤더니 10억을 루트를 씌우면 대충 32000(?) 정도 나온다 그렇다면 이 소수보다 커지는 두개의 소수는 1e+9 보다 커지게 되므로, 10억에 루트를 씌운 값보다 큰 소인수를 2개를 가지면 아예 입력으로 주어질 수 없다는 걸 생각했음........

그래서 소수를 vector에 저장하고, 그 모아놓은 소수 내에 소인수가 존재하지 않으면 그 수는 그냥 소수다 라고 생각했는데

그리고 그렇게 짜고나서 또 틀렸습니다를 받았다. 생각해보니 저렇게 생각했으면서 코드부분에 추가를 안해놔서 그랬던 거다.....

지금 이게 학교 실습문제로 나왔다던데.....

BOJ에 막 제출하고 있는데 일단 코드는 오늘 12시 넘어서 올려야 할 것 같다........

마지막에 제출한 코드에서 4줄? 정도 추가하면 정답이 나오는데..... 음... 

코드가 난잡해서 나도 약간 이쁘게 수정해봐야겠다.

#include<cstdio>
#include<vector>
 
using namespace std;
typedef long long lld;
typedef vector<lld> VLL;
typedef vector<bool> VB;
 
VLL factors;
lld ans;
lld A, B, N;
 
lld IE_function(lld facts, int e, int index){
    lld ret = 0;
    if(e%2==1){ // minus
        for(int i = index+1 ; i < factors.size() ; i++) 
            ret += IE_function(facts * factors[i], e+1, i); // lld next_factor = factors[i];
        ret -= (B/facts - (A-1)/facts);
    }else if(e%2==0){ // plus
        for(int i = index+1 ; i < factors.size() ; i++) 
            ret += IE_function(facts * factors[i], e+1, i); // lld next_factor = factors[i];
        ret += (B/facts - (A-1)/facts);
    }
    return ret;
} // inclusionexclusion
 
int main(){
    int n;
    int c = 1;
    VB is_not_prime = VB(88888, false);
    VLL prime = VLL(0);
 
    for(int i = 2 ; i < 33333 ; i++){
        int num = i+i;
        if(!is_not_prime[i]) prime.push_back(i);
 
        while(!is_not_prime[num] && num < 33333){
            is_not_prime[num] = true;
            num += i;
        }
    }
 
    for(scanf("%d", &n) ; n-- ; ){
        factors = VLL(0);
        scanf("%lld%lld%lld",&A,&B,&N);
        ans = B-A+1;
 
        if(N==1){
            printf("Case #%d: %lld\n",c++ , ans);
            continue;
        } // except case N==1 
 
        for(auto iter = prime.begin() ; iter != prime.end() ; iter++){
            lld p = *iter;
            if( (N%p) == 0 ){
                factors.push_back(p);
                while(N%p==0) N/=p;
            }
            if(N==1) break;
        }
        if(N!=1) factors.push_back(N);
        // factorization in prime factors
 
        for(int i = 0 ; i < factors.size() ; i++){
            lld fac = factors[i];
            ans += IE_function(fac, 1, i);
        }
        // inclusionexclusion
 
        printf("Case #%d: %lld\n",c++, ans);
    }
    return 0;
}