포함-배제의 원리

포함배제의 원리는 여러개의 집합이 있고, 각 집합간의 교집합에 속하는 원소의 개수를 알 때, 총 합집합의 원소의 개수를 구하는 방법이다.

 

집합이 두개나 세개일 때 구하는 방법은 중학교 수학시간에 배웠다.

집합이 두개(A,B) 일 때는 |A합B| = |A|+|B|-|A교B|이고,

세개(A,B,C)일 때는 |A합B합C| = |A|+|B|+|C|-|A교B|-|B교C|-|A교C|+|A교B교C| 로 구할 수 있다.

 

그렇다면 집합의 개수가 이보다 더 많아질 때는 어떻게 계산할까? 

집합의 개수가 n개일 때 합집합을 구하는 공식은 3개일 때의 공식에서 보면 살짝 유추할 수 있는데, 

바로 집합의 교집합이 홀수개일 때는 더하고, 짝수개일 때는 빼는 것이다. A,B,C와 A교B교C교는 홀수개였으므로 더했고 A교B, B교C, A교 C는 짝수개였으므로 뺀 것이다. 이를 수식으로 정리하면 다음과 같다.

 

여기서 한가지 주의해야 할 것은, 공식에서 보다시피 계산을 하기 위해서는 개수별로 집합간의 모든 combination의 경우의 수를 다 살펴보아야 한다. 즉 원소가 n개인 집합의 모든 부분집합을 봐야 한다는 의미이므로 총 2^n개를 봐야한다는 뜻이다. 그래서 n=23정도 까지만 직접 계산을 할 수가 있다.

 

 

[BOJ 17436] 소수의 배수 - G3

 

소수가 n개 주어지고 그 n개의 소수 중에서 적어도 하나의 소수로 나눠 떨어지는 1~end 까지의 수가 총 몇개인지를 구하는 문제이다.

소수의 집합을 p1,p2,...p_n이라고 한다면 |p1합p2합...합p_n|을 구하는 것이 이 문제의 목표이다. 따라서 위의 공식을 그대로 갖다쓰기만 하면 된다. 1~n까지 x의 배수의 개수는 n/x로 간단히 구할 수 있다.

 

vector<int> factor;

ll getCount(ll end){
    int sz=factor.size();
    ll cnt=0;
    for(int i=1 ; i<(1<<sz) ; i++){
        ll mul=1,sub=0;
        for(int j=0 ; j<sz ; j++){
            if(i&(1<<j)){
                mul*=factor[j];
                sub++;
            }
        }
        ll res=end/mul;
        if(sub%2==0) res=-res;
        cnt+=res;
    }    
    return cnt;
}

int main(){
    int n; ll end,ans=0;   scanf("%d %lld",&n,&end);

    for(int i=1 ; i<=n ; i++){
        int inp;    scanf("%d",&inp);
        factor.push_back(inp);
    }
    ans=getCount(end);
    printf("%lld\n",ans);

    return 0;
}

 

 

[BOJ 9359] 서로소 - G3

 

이 문제도 위에서 설명했던 문제랑 유사한데, 이번에는 여러개의 소수를 직접 알려주는 것이 아니라 임의의 수n을 던져주고 그 수를 본인이 직접 알아서 소인수분해하여 소수를 뽑아내야 한다. 그리고 n으로 나눠 떨어지는 수의 개수가 아닌 서로소의 개수를 묻고 있다. 따라서 방금 위에서 구한 집합의 여집합(complement)을 구해야 하는 것이다. 또한 이 문제는 1~end까지를 묻는게 아닌 st~end를 묻고 있다. 즉, 시작 수와 끝수 모두 변수이다. 사실 조금만 생각해보면 st~end=(1~end)-(1~st)로 유도할 수 있다.

vector<int> factor;

ll getCount(ll end,ll x){
    int sz=factor.size();
    ll cnt=0;
    for(int i=1 ; i<(1<<sz) ; i++){
        ll mul=1,sub=0;
        for(int j=0 ; j<sz ; j++){
            if(i&(1<<j)){
                mul*=factor[j];
                sub++;
            }
        }
        ll res=end/mul;
        if(sub%2==0) res=-res;
        cnt+=res;
    }    
    return end-cnt;
}

int main(){
    int t;  scanf("%d",&t);

    int trial=1;
    while(t--){
        ll a,b,n,ans=0;   scanf("%lld %lld %lld",&a,&b,&n);
        ll tmp=n;

        for(int i=2 ; i*i<=n ; i++){
            if(n%i==0) factor.push_back(i);
            while(n%i==0){
                n/=i;
            }
        }
        if(n!=1) factor.push_back(n);
        n=tmp;
        assert(factor.size()<=20);

        ans=getCount(b,n)-getCount(a-1,n);
        printf("Case #%d: %lld\n",trial++,ans);
        factor.clear();
    }

    return 0;
}