백준 14858번 GCD 테이블과 연속 부분 수열

문제 요약

$G[i][j]$에 $GCD(i,j)$가 저장되어 있는 크기 $N \times M$의 배열이 있다. 길이 $k$인 수열 $a_1, a_2, ... a_k$가 주어졌을 때, 배열 G에서 연속한 부분 수열들 중에서 $a_1, a_2, ... , a_k$가 존재하는지 아닌지를 구해야 한다.

조건은 $1 \le N,M \le 10^{12}, \; 1 \le i \le N, \; 1 \le j \le M, \; 1 \le k \le 10000$이다.

문제 풀이

일단 첨자표시가 마크다운에선 좀 쓰기 힘드니 $G[i][j]$대신 $G(i,j)$로 쓰겠다.

문제를 다시 적어보자면, $1 \le l \le k$인 $l$에 대하여 $G(x,y+l) = a_l$인 $(x,y)$를 찾는 것이라고 생각하면 된다. 여기서 $x$와 $y$의 범위는 $1 \le x \le N, \; 0 \le y \le M-k$이다.

일단, $x$부터 살펴보도록 하자. G배열 상에서 행에서 연속한 부분 수열을 찾는 것이기 때문에 우리가 원하는 연속 부분 수열이 존재한다면, $x$는 고정값이 될 것이다.

이를 잘 생각해보면 $x$는 모든 $a_i$를 약수로 가지는 숫자여야만 한다. 왜냐면 $G(x,y)$는 $x$와 $y$의 최대공약수이고, 주어진 수열이 G상에서 연속 부분 수열로 존재한다면 $x$는 모든 $a_i$로 나누어 떨어지는 수라는 말이 된다.

따라서 $x$는 모든 $a_i$를 약수로 가져야 하며, 그러한 수를 생각해보면 $LCM(a_1, a_2, ... , a_k)$의 배수임을 알 수 있다. 이 최소공배수를 $L$이라고 하자. 그러면 $x$는 이 $L$의 배수 중에 하나가 되야 할 것이다. 그리고

이제 $y$를 보자. $G(x,y+l)$이 $a_l$이라는 소리는 $y+l$은 $a_l$로 나누어 떨어진다는 소리다. 이를 합동식으로 표현해보면 아래와 같다.

$$
\begin{aligned}
y+1 &\equiv 0 \; (mod \; a_1) \\
y+2 &\equiv 0 \; (mod \; a_2) \\
& \qquad\vdots \\
y+k &\equiv 0 \; (mod \; a_k)
\end{aligned}
$$

우리가 원하는 $y$는 위 $k$개의 합동식을 만족하는 $y$인 것이다. $k$개의 합동식을 푸는 것은 중국인의 나머지 정리를 이용하면 가능하다.

그러면 이제 답을 구할 수 있다. $x$는 주어진 수열들의 최소공배수의 배수임을 알았고, $y$는 위 $k$개의 합동식을 만족하는 값이다.

이제 시간 복잡도를 계산하자. $x$를 구하는데에 필요한$LCM(a_1, a_2, a_3, ... , a_k)$를 구하는 데에는 $O(klogL)$이 걸릴 것이고, $y$를 구하는 데에도 $O(klogL)$만큼 시간이 걸릴 것이다.

이 때, $L$이 $N$을 넘어가면 우리가 원하는 $x$가 없다는 뜻이다. 그리고 합동식의 해가 없다면 우리가 원하는 $y$가 없다는 뜻이다. 이를 통해서 잘 커팅해주면 $L$의 범위는 $N$의 범위와 같기 때문에 충분히 시간 안에 답을 구할 수 있다.

이러한 방법들로 $(x,y)$를 구한 뒤에 $1 \le x \le N, \; 0 \le y \le M-k$라면 답은 YES고, 아니라면 NO이다.

아래는 코드다. 오버플로우를 방지하기 위해 __int128_t를 사용했다.

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

pair<ll,pair<ll,ll>> xGCD(ll a, ll b) {
    if(b == 0) return {a,{1,0}};
    pair<ll,pair<ll,ll>> ret = xGCD(b, a%b);
    ll g, x, y;
    g = ret.first;
    tie(x,y) = ret.second;
    return {g,{y,x-(a/b)*y}};   
}

pair<ll,ll> CRT(vector<ll> &A, vector<ll> &M) {
    if(A.size() != M.size()) return {-1,-1};
    int N = A.size();
    ll a1 = A[0];
    ll m1 = M[0];
    for(int i=1;i<N;++i) {
        ll a2 = A[i];
        ll m2 = M[i];
        a2 %= m2;
        ll g = __gcd(m1, m2);
        if(a1 % g != a2 % g) return {-1,-1};
        ll p, q;
        auto res = xGCD(m1/g, m2/g);
        tie(p,q) = res.second;
        i128 mod = (i128)m1 / g * m2;
        a1 = ((i128)a1 * (m2/g) % mod) * q % mod + ((i128)a2*(m1/g)%mod)*p % mod;
        a1 = (a1 + mod) % mod;
        m1 = mod;
    }
    return {a1, m1};
}

bool check(vector<ll> &a, ll N) {
    i128 L = a[0];
    for(int i=1;i<a.size();++i) {
        i128 g = __gcd(L,(i128)a[i]);
        L = L / g * a[i];
        if(L > N) return false;
    }
    return true;
}

ll N, M;
int K;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M >> K;
    vector<ll> a(K);
    for(int i=0;i<K;++i) cin >> a[i];
    if(!check(a,N)) {
        cout << "NO" << '\n';
        return 0;
    }
    vector<ll> A(K);
    for(int i=0;i<K;++i) {
        ll l = -(i+1);
        l -= (l/a[i]) * a[i];
        l += a[i];
        l %= a[i];
        A[i] = l;
    }
    ll x, m;
    tie(x,m) = CRT(A, a);
    if(x == -1 || x > M-K) {
        cout << "NO" << '\n';
        return 0;
    }
    for(ll i=1;i<=K;++i) {
        if(__gcd(m, x+i) != a[i-1]) {
            cout << "NO" << '\n';
            return 0;
        }
    }
    cout << "YES" << '\n';
    return 0;
}