けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Judge System Update Test Contest 202004 D - Calculating GCD (400 点)

面白かった

問題へのリンク

問題概要

 N 要素からなる正の整数列  A_{1}, \dots, A_{N} が与えられる。以下の  Q 個のクエリに答えよ

  • 各クエリは整数  x が与えられる
  •  i = 1, 2, \dots, N の順に、 x = {\rm GCD}(x, A_{i}) という更新を行う
    • 初めて  x = 1 となる瞬間の  i を求めよ
    • 終結果が 1 より大きいときは、その値を答えよ

制約

  •  1 \le N, Q \le 10^{5}

解法 (1): 二分探索

一般に、

  •  {\rm GCD}({\rm GCD}(x, A_{1}), A_{2}) = {\rm GCD}(x, {\rm GCD}(A_{1}, A_{2}))

といったことが成り立つ。よって、

  •  B_{1} = A_{1}
  •  B_{2} = {\rm GCD}(A_{1}, A_{2})
  •  B_{3} = {\rm GCD}(A_{1}, A_{2}, A_{3})
  • ...

としてあげて、 i 回目の操作は

  •  x = {\rm GCD}(x, B_{i})

という風に書くことができる。

B の性質を用いて二分探索

 B は、約数倍数的な意味で単調減少になっている。 B_{i+1} B_{i} の約数になっているのだ。
よって、 x i に対して、単調減少だ。よって以下のような二分探索で答えを求めることができる。


 {\rm GCD}(x, B_{i}) = 1 となるような最小の  i を求める


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

long long GCD(long long x, long long y) {
    if (y == 0) return x;
    else return GCD(y, x%y);
}

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 1; i < N; ++i) A[i] = GCD(A[i-1], A[i]);

    for (int _ = 0; _ < Q; ++_) {
        long long x; cin >> x;
        int left = -1, right = N;
        while (right - left > 1) {
            long long mid = (left + right) / 2;
            long long g = GCD(x, A[mid]);
            if (g == 1) right = mid;
            else left = mid;
        }
        if (right == N) cout << GCD(A.back(), x) << endl;
        else cout << right + 1 << endl;
    }
}

解法 (2): ランレングス圧縮

B をランレングス圧縮すると、B の値の変わり目の個数が log オーダーなので、愚直にやっても通る。

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

long long GCD(long long x, long long y) {
    if (y == 0) return x;
    else return GCD(y, x%y);
}

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 1; i < N; ++i) A[i] = GCD(A[i-1], A[i]);

    vector<pair<long long, int> > AA;
    for (int i = 0; i < N;) {
        int j = i;
        while (j < N && A[i] == A[j]) ++j;
        AA.push_back({A[i], i});
        i = j;
    }

    for (int _ = 0; _ < Q; ++_) {
        long long x; cin >> x;
        long long res = GCD(A.back(), x);
        for (auto p : AA) {
            if (GCD(p.first, x) == 1) {
                res = p.second + 1;
                break;
            }
        }
        cout << res << endl;
    }
}