[C++] 백준 1441 나누어 질까

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

1441번: 나누어 질까

 

 

 

먼저 R제한이 10^9이기 때문에 원소를 받아 직접 에라체를 만드는 것은 불가능하다.

따라서 비트마스킹을 이용한 포함 배제의 원리를 사용하여 풀었다.

 

N이 18이기 때문에 2^18로 시간 내에 충분히 해낼 수 있다.

 

한 가지 조심해야 하는 점이 있는데

수열의 각 원소의 제한은 10^9이므로

원소간의 lcm이 R을 넘어가는 경우 멈춰주어야 한다.

예를들어 원소로 10^9-1, 10^9-2, 10^9-3...이 들어오게 된다면

자료형을 long long으로 잡아도 오버플로우가 충분히 날 수 있기 때문이다.

 

정답코드

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

const ll mod = 1e9+7;


ll gcd(ll a, ll b) {
    if (b) return gcd(b, a%b);
    return a;
}

ll ceil(ll a, ll b) {
    return (a-1)/b + 1;
}

void debug() {

}



ll N, L, R;
ll arr[20];

void solve() {
    cin >> N >> L >> R;
    for (ll i = 0; i < N; i++) cin >> arr[i];
    ll ans = 0;
    for (ll bit = 1; bit < (1<<N); bit++) {
        ll temp = 1, flag = 1, cnt = 0;
        for (ll i = 0; i < N; i++) {
            if ((1<<i) & bit) {
                temp = temp*arr[i]/gcd(arr[i], temp);
                cnt++;
                if (temp > R) {
                    flag = 0; 
                    break;
                }
            }
        }
        if (!flag) continue;
        if (cnt & 1) ans += R/temp - (L-1)/temp;
        else ans -= R/temp - (L-1)/temp;
    }
    cout << ans << '\n';
}



int main() {
    FASTIO
    ll T=1;
    while (T--) solve();
} 

 

사실 포함배제에 꿀문제들이 많은 것 같다.

맨날 풀어야지