정수론 포함 배제의 원리 꿀 문제 모음

1. 서로소

https://www.acmicpc.net/problem/9359

포함 배제의 원리를 사용하는 정수론 문제.

포함 배제를 사용해 풀고 있었는데 계속 WA를 받아서 답을 봤더니

포함 배제를 통한 접근이 맞아서 기분이 좋았다.

하지만 포함 배제하는 과정에서 부분 수열의 개수를 구하는 과정이 틀려

WA를 받았다.

문제 접근

주어진 범위와 그 범위에 있는 수 $x\in [a-1,b]$에 대해

$gcd(N,x)=1$이어야 하기 때문에

$N$의 소인수들의 배수를 제외해주면 된다.

소인수들의 배수를 제외하는 과정에서 소인수들의 곱으로 생기는 수도

중복으로 제외되므로 이 점을 유의해서 제거해야 한다.

BOJ Jealous Numbers 는 $p,q$ 만 있어 더 쉽게 풀 수 있다.

소인수들의 곱으로 생기는 수의 경우들을 살펴보자

소인수 집합 $\mathbb{P}$에 대해

$\mathbb{P}=\{2,3,5\}$

일 때 알고리즘의 진행은

1. $2,3,5$ 배수 제거

2. $2\times3,2\times5,3\times5$가 2번씩 제거되었으므로 추가

3. $2\times3\times5$가 $2,3,5$에 의해 3번 제거되고

   $2\times3,2\times5,3\times5$ 에 의해 추가되었으므로

   제거되지 않은 $2\times3\times5$의 배수들의 개수를 제거해준다.

이번에는 $\mathbb{P}=\{3,5,7,11\}$ 을 보자.

1. $3,5,7,11$ 제거

2. $3\times5,3\times7,3\times11,5\times7,5\times11,7\times11$ 추가

3. $3\times5\times7,3\times5\times11,5\times7\times11$ 제거

4. $3\times5\times7\times11$의 배수는 1번에서 4번 제거, 2번 과정에서 6번 추가

   3번 과정에서 4번 제거 되었다. 최종적으로 2번 제거된 상태이므로

   한번 추가해주면 된다.

살펴본 결과 소수의 곱으로 이루어진 수에 대해 소수의 개수가 짝수면 더해주고

홀수면 빼주면 된다는 것을 알게 되었다.

따라서 모든 조합에 대해 이를 수행해주면 된다.

모든 부분 소수 조합의 개수는 $2^{n(\mathbb{P})}-1$이다.($\{0\}$ 제외)

이것을 깔끔하고 아름답게 처리하는 방법은 비트마스킹을 사용하는 것이다.

각각의 경우에 따라 소수들을 곱해준 다음, 위 과정으로 해결해주면 되겠다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll a,b,n;

ll solve(ll n, vector<int> &p){
    ll res=n;
    int cnt=1<<p.size();
    for(int i=1;i<cnt;i++){
        ll div=1;
        bool odd=0;
        int j=i;
        int idx=0;
        while(j){
            if(j&1){
                div*=p[idx];
                odd=!odd;
            }
            idx++;
            j>>=1;
        }
        if(odd) res-=n/div;
        else res+=n/div;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin >> t;
    for(int tt=0;tt<t;tt++){
        vector<int> p;
        cin >> a >> b >> n;
        int cnt=sqrt(n);
        for(int i=2;i<=cnt;i++){
            if(n%i==0){
                p.push_back(i);
                while(n%i==0) n/=i;
            }
        }
        if(n>1) p.push_back(n);
        cout << "Case #" << tt+1 << ": " << solve(b,p)-solve(a-1,p) << '\n';
    }
    return 0;
}

2. 소수의 배수

https://www.acmicpc.net/problem/17436

이 문제는 위에 있는 서로소 문제에 $p$ 배열을 준 문제 + $\alpha$ 라서 설명을 생략하겠다.

3. 나누어 질까

이 문제 생김새가 서로소랑 똑같이 생겼는데

잡생각이 많이 들어 WA를 받은 문제이다.

단순명료하게 생각했으면 쉽게 풀었을 것 같은 문제이다.

문제 접근

처음에는 "$\mathbb{P}$가 unique해야 된다." 부터 시작해서

"$a|b$ 인 소수 a만 살리자..." 등등 별 잡생각이 들었지만 핵심은 $LCM()$이었다.

직관적으로 다가오지는 않지만

이 문제도 겹치는 배수 처리 방식이 서로소 문제와 같다.

$a,b,c,n\in \mathbb{N}$ 에 대해

$n$ 이하 $a,b,c$ 의 배수를 각각 지우면 $lcm(a,b),lcm(a,c),lcm(b,c)$은

두 번 세어졌으므로

$lcm(a,b),lcm(a,c),lcm(b,c)$를 한 번씩 빼준다.

$lcm(a,b,c)$ 는 3번 추가, 3번 빠졌으므로 한번 더해준다.

이 문제 역시 홀수 개수 곱은 더해주고 짝수 개수 곱은 빼주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    ll l,r;
    cin >> n >> l >> r;
    vector<int> a(n);
    l--;
    for(int &t:a) cin >> t;
    ll lans=0,rans=0;
    int cnt=1<<a.size();
    for(int i=1;i<cnt;i++){
        int j=i;
        int idx=0;
        bool odd=0;
        ll div=1;
        while(j){
            if(j&1){
                div=lcm(div,a[idx]);
                odd^=1;
            }
            idx++;
            j>>=1;
        }
        if(odd){
            lans+=l/div;
            rans+=r/div;
        }
        else{
            lans-=l/div;
            rans-=r/div;
        }
    }
    cout << rans-lans;
    return 0;
}