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

面白かった

問題へのリンク

問題概要

要素からなる正の整数列 が与えられる。以下の 個のクエリに答えよ

• 各クエリは整数 が与えられる
• の順に、 という更新を行う
  • 初めて となる瞬間の を求めよ
  • 最終結果が 1 より大きいときは、その値を答えよ

制約

• 

解法 (1): 二分探索

一般に、

• 

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

• 
• 
• 
• ...

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

• 

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

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

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

---

となるような最小の を求める

---

#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;
    }
}