24551번: 일이 너무 많아... - 조합론(포함-배제 정리)

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

24551번: 일이 너무 많아...

\(N\)이 굉장히 크기 때문에 완전 탐색, 에라토스테네스의 체 등 \(O(N)\) 정도의 시간복잡도를 가지는 알고리즘으로는 해결할 수 없다. 

 

11로 나눠지는 수의 집합을 A, 111로 나눠지는 수의 집합을 B라 한다면, 11과 111로 나눠지는 수의 집합은 A와 B의 합집합이다. 이 문제는 이러한 집합의 수가 여러 개로 확장된 것이므로, 이 문제는 포함-배제 정리로 해결할 수 있다.

단, {1111, 11}과 같이 두 수를 나누었을 때 나머지가 0이라면 한 집합이 다른 집합에 포함되어 버리므로, 1111은 집합으로 표현하지 말아야 한다.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

ll N;
vector<ll> v;
ll ans = 0;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N;
    string s = "11";
    while (N >= stoll(s))
    {
        bool check = true;
        for (ll val : v)
        {
            if (stoll(s) % val == 0)
            {
                check = false;
                break;
            }
        }

        if (check)
            v.push_back(stoll(s));
        s += '1';
    }

    for (int S{1}; S < (1 << v.size()); S++)
    {
        int cnt = 0;
        ll val = 1;
        bool tooBig = false;

        for (int i{0}; (1 << i) <= S; i++)
        {
            if (S & (1 << i))
            {
                if (N / v[i] < val)
                {
                    tooBig = true;
                    break;
                }
                val *= v[i];
                cnt++;
            }
        }

        if (tooBig)
            continue;

        if (cnt % 2)
            ans += N / val;
        else
            ans -= N / val;
    }
    cout << ans << "\n";
}