CF#691Div.2とABC186でGCD問題が解けなかったので復習する

Codeforces Round #691 (Div. 2)のC問題で最大公約数（GCD）の問題が出た。 パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）のE問題で拡張ユークリッドの互除法が出た。

どちらも解けなかった（は？）。 CFは1592→1575（-17）、ACはパフォーマンス955で困る。

復習します。

C. Row GCD

問題のリンク 解説のリンク

解説によるとらしいです。

証明してみるか。

---

をの倍数のとき、はの倍数。→。

をの倍数のとき、はの倍数。→。

ゆえに。

---

あとは解説の通りに実装。

コンテスト中は鳩の巣原理・周期性について考えていた。

コード

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

// 解法は公式tutorialを見て
// https://codeforces.com/blog/entry/85750

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> b(m);
    for (int i = 0; i < m; i++) cin >> b[i];

    sort(a.begin(), a.end());

    // gcd(a[i] - a[0])
    int gcd_ai_a0 = 0;
    for (auto &&i : a) {
        gcd_ai_a0 = gcd(i - a.front(), gcd_ai_a0);
    }

    vector<int> answers;
    answers.reserve(m);

    for (auto &&bi : b) {
        const int ans = gcd(a.front() + bi, gcd_ai_a0);
        answers.emplace_back(ans);
    }

    for (auto i = answers.begin(); i != answers.end(); i++) {
        cout << *i << (i != answers.end() - 1 ? ' ' : '\n');
    }
}

E - Throne

問題のリンク snukeの公式解説放送 公式解説

拡張ユークリッドの互除法が出てきます。 これらで拡張ユークリッドの互除法を勉強した。

• drkenの記事はけっこうわかりやすいです。
• snukeの公式解説放送は良いと思う。
• 蟻本は書くべきことは書いてある。行間が飛んでるかなと思う。

拡張ユークリッドの互除法を使えば、を満たすを高速に求められる。

これでユークリッドの互除法の理解は十分だな。 公式解説を見ながら問題を解いていきます。

回の行動で玉座に座れることとが成り立つことは同値です。
よって「となる最小のを求めよ」という形の問題が解ければよいです。この問題は次のように解くことができます。
（中略）
3. のとき、におけるの逆元をとして、が解
（略）
https://atcoder.jp/contests/abc186/editorial/401より引用。アクセス日は2020年12月23日。

1. 拡張ユークリッドの互除法を使えば、を満たすを高速に求められる。
2. ならば、を満たすはである。
3. ならば、の逆元は存在しない。

解説でで割っているのは完全には理解していない。 となるを求めるときに2で割るのかー。

コード

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

// solve a testcase
void solve();

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int t;  // number of testcases
    cin >> t;
    // solve all testcases
    for (int i = 0; i < t; i++) {
        solve();
    }
}

// this function is copied from :https://www.youtube.com/watch?v=hY2FicqnAcc&feature=youtu.be
tuple<int, int, int> extgcd(int a, int b) {
    if (b == 0) return {a, 1, 0};
    int g, x, y;
    tie(g, x, y) = extgcd(b, a % b);
    return {g, y, x - a / b * y};
}
// end of copy

void solve() {
    int n, s, k;
    cin >> n >> s >> k;

    // s + xk = 0 mod n
    // を満たす最小のxを求める。

    // xk = -s mod n
    // Ax = B mod M

    int a = k;
    int b = -s;
    int m = n;

    // bを正にする
    while (b < 0) {
        b += n;
    }

    // 割っておく
    {
        const int g = gcd(a, gcd(b, m));
        a /= g, b /= g, m /= g;
    }

    // Aのmod Mの逆元を探す
    // gcd(A, M)!=0なら存在しない

    if (gcd(a, m) != 1) {
        cout << -1 << "\n";
        return;
    }

    // Aのmod Mの逆元は
    // Ax + My = gcd(A, M) = 1
    // を満たすx,yを拡張ユークリッドの互除法で計算して、そのx
    int x, y, g;
    tie(g, x, y) = extgcd(a, m);

    while (x < 0) {
        x += m;
    }

    int ans = x * b % m;
    cout << ans << "\n";
}

// thx
//
// 解説放送
// https://www.youtube.com/watch?v=hY2FicqnAcc&feature=youtu.be
// かいせつ
// https://atcoder.jp/contests/abc186/editorial/401
// drkenの記事
// https://qiita.com/drken/items/b97ff231e43bce50199a
// 蟻本

おまけ

証明ミスがあったら教えて下さい。