백준 21088번 Remove the Prime

문제 요약

수가 n개 주어진다. 어떤 소수 p와 연속적인 구간[l,r]을 선택할 수 있는데, 해당 구간에 있는 모든 수들이 p로 나눠져야 한다.

p와 [l,r]을 골랐으면 해당 구간의 수들에서 소인 수 p를 지운다. $a_l, a_{l+1}, \ldots , a_r$에 대해서 p로 더이상 나눠지지 않을 때 까지 p로 나누는 것과 같다.

두 플레이어가 번갈아가면서 위와 같은 선택을 하는 게임을 진행한다고 하자. 그리고 행동을 취할 수 없으면 지는 게임이다.

두 플레이어가 최적으로 게임을 진행했을 때, 승자를 결정하시오.

$ n \le 1000$, $ 1 \le a_i \le 10^{18}$.

풀이

이 문제에 대해서 알고 있는 풀이가 두 개 있는데 코드 짜기가 힘들지만 생각하기 쉬운 풀이부터 소개한다.

먼저, $a_i$를 시간내에 잘 소인수 분해를 했다고 하자. 폴라드 로가 대략 $O(n^{\frac{1}{4}}logn)$이니까 숫자 1000개를 6초 내에 소인수 분해하는 것을 잘 해줄 거 같다.

그럼 문제에서 제시한 게임에 대해서 분석을 해봐야 하는데, 어떤 소수 $p$가 연속적으로 존재하는 구간을 생각해보자.

이 구간 하나를 하나의 돌무더기가 있는 님 게임으로 생각할 수 있다. 그런 구간의 길이를 $L$이라고 하면 그 님게임의 그런디 수도 $L$이 된다.

따라서, 소인수분해를 빠른 시간내에 해내서 모든 소인수를 찾고, 각 소인수에 대해서 그 소인수가 존재하는 연속구간들만 전부 찾아내고 XOR을 취해주면 게임의 승자를 판단할 수 있다.

여기서 연속적인 구간을 판단하는게 시간이 얼마나 걸릴지 생각해보자.

모든 수를 소인수분해한 결과 나온 소인수들의 종류의 수를 $\vert P \vert$라고 하면, 걸리는 시간은 $O(\vert P \vert n)$이 된다. 저 P 값은 $O(n)$정도 일테니까 $O(n^2)$이면 답을 구할 수 있다.

여기서 중요한 게 있다. 소인수 분해를 적절히 빠르게 해내야 한다. 위에서 명시한 폴라드 로의 시간복잡도 상으론 대충 잘 돌아가지 않나? 라고 생각하기 쉽다.(나도 그랬다.)

근데 폴라드 로를 정말 잘 짜야 시간 내에 돈다. 내 손으로 짠 폴라드 로는 당연히 터졌고 찾다가 KACTL의 구현체를 가져다 쓰니 시간 내에 잘 돌아갔다.

다른 풀이는 300만 이하의 소수들을 에라토스테네스의 체로 전부 구하고 수들을 이 소수들로 소인수분해한다.

이 과정을 진행한 다음에 소인수분해가 완료되지 않은 수들은 세가지 종류밖에 없다.

$p, p^2, pq$로 소수 하나거나, 소수의 제곱이거나 두 소수의 곱이다.

그러면 그냥 적절하게 소수 하나면 밀러라빈으로 체크 가능하고, 소수의 제곱이거나 두 소수의 곱이라면 이 소인수는 $10^9$이하면서 300만보다 큰 소수일테니 폴라드 로를 돌리면 $O(\sqrt{p})$정도에 돌 것이다. 이렇게 모든 소인수 분해를 마치면 게임과 관련된 부분은 동일하다.

이 풀이는 내가 낸게 아니라 샘터의 풀이를 들은 것이므로 부정확한 부분이 있을 수 있다. 특히 뒤에 $p, p^2, pq$는 폴라드 로로 잘 찾아질 것이라는 거는 쌩 뇌피셜이다. 사실 풀이는 너무 맞는 풀이이기 때문에 맞을 거 같다. 샘터가 AC도 받아놨고.

아래 코드는 폴라드로를 사용해서 썡으로 소인수 분해 다 하는 코드다.

#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef unsigned long long ull;

// from https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/
ull bgcd(ull u, ull v) {
  int shift;
    if (u == 0) return v;
    if (v == 0) return u;
    shift = __builtin_ctz(u | v);
    u >>= __builtin_ctz(u);
    do {
        v >>= __builtin_ctz(v);
        if (u > v) {
            ull t = v;
            v = u;
            u = t;
        }  
        v = v - u;
    } while (v != 0);
    return u << shift;
}
// from https://github.com/kth-competitive-programming/kactl/blob/master/content/number-theory/ModMulLL.h
ull modmul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(1.L / M * a * b);
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = modmul(b, b, mod), e /= 2)
        if (e & 1) ans = modmul(ans, b, mod);
    return ans;
}
// from https://github.com/kth-competitive-programming/kactl/blob/master/content/number-theory/MillerRabin.h
bool isPrime(ull n) {
    if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
    static ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    ull s = __builtin_ctzll(n-1), d = n >> s;
    for (ull a : A) {   // ^ count trailing zeroes
        ull p = modpow(a%n, d, n), i = s;
        while (p != 1 && p != n - 1 && a % n && i--)
            p = modmul(p, p, n);
        if (p != n-1 && i != s) return 0;
    }
    return 1;
}
// from https://github.com/kth-competitive-programming/kactl/blob/master/content/number-theory/Factor.h
ull pollard(ull n) {
    auto f = [n](ull x) { return modmul(x, x, n) + 1; };
    ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
    while (t++ % 40 || bgcd(prd, n) == 1) {
        if (x == y) x = ++i, y = f(x);
        if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
        x = f(x), y = f(f(y));
    }
    return bgcd(prd, n);
}
vector<ull> factor(ull n) {
    if (n == 1) return {};
    if (isPrime(n)) return {n};
    ull x = pollard(n);
    auto l = factor(x), r = factor(n / x);
    l.insert(l.end(), all(r));
    return l;
}

int N;
ull a[1005];
unordered_set<ull> s;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for(int i=0;i<N;++i) cin >> a[i];
    for(int i=0;i<N;++i) {
        vector<ull> factors = factor(a[i]);
        for(const ull &p : factors) s.insert(p);
    }
    ull ans = 0;
    for(auto it=s.begin();it!=s.end();++it) {
        int len = 0;
        ull p = *it;
        for(int i=0;i<N;++i) {
            if(modmul(a[i], 1, p) == 0) ++len;
            else {
                ans ^= len;
                len = 0;
            }
        }
        ans ^= len;
    }
    if(ans) cout << "First" << '\n';
    else cout << "Second" << '\n';
    return 0;
}