C++の練習を兼ねて, AtCoder Beginner Contest 186 の 問題E (Throne) を解いてみた.
■感想.
1. 問題E は, 解答方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できたので良かったと思う.
2. 拡張ユークリッドの互除法という新しい知識が増えたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 186 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
// 解き直し. // https://atcoder.jp/contests/abc186/editorial/401 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) // Function for extended Euclidean Algorithm // https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended/ // a * x + b * y = gcd(a, b) となる (x, y) を 計算. // @param a: 方程式の係数. // @param b: 方程式の係数. // @param *x: 方程式の解. // @param *y: 方程式の解. // @return: 結果. LL gcdEx(LL a, LL b, LL *x, LL *y){ // base case. if(a == 0){ *x = 0; *y = 1; return b; } // to store results of recursive call. LL x1, y1; LL gcd = gcdEx(b % a, a, &x1, &y1); // update x and y using results of recursive call. *x = y1 - (b / a) * x1; *y = x1; return gcd; } int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. クエリ回答. rep(i, T){ LL N, S, K; scanf("%lld %lld %lld", &N, &S, &K); // 2-1. A = K, B = N - S, M = N と置いて計算. LL A = K, B = N - S, M = N; LL d = __gcd(A, B); d = __gcd(d, M); // 2-2. 置き換え. A /= d; B /= d; M /= d; // 2-3. 判定. LL g = __gcd(A, M); // 2-4. 解なし. if(g != 1LL){ puts("-1"); continue; } // 2-5. 解あり. LL x, y; LL gam = gcdEx(A, M, &x, &y); while(x < 0) x += M; // A の 逆元. x = x * B % M; printf("%lld\n", x); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
[入力例] 4 10 4 3 1000 11 2 998244353 897581057 595591169 10000 6 14 [出力例] 2 -1 249561088 3571 ※AtCoderテストケースより [入力例] 20 95 84 82 144 87 36 115 78 48 142 43 95 72 45 94 1485 878 517 622 318 692 269 224 3 795 403 553 633 451 695 8982 5831 368 15547 10707 2135 6564 3533 4354 57018 17154 57943 1002732 227363 1141827 119772982 52299780 115946035 151870020 83977522 26016849 140146322 86569205 56911491 159629599 118049326 107922709 93695274 15789770 68582371 [出力例] 43 -1 99 13 -1 -1 31 15 524 493 -1 -1 -1 35610 -1 65681178 -1 8482495 39780251 85958044 |
■参照サイト
パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）
Function for extended Euclidean Algorithm