C++の練習を兼ねて, AtCoder Regular Contest 050 の 問題C (LCM 111) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 行列累乗について復習出来たので, 非常に良かったと思う..
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 050 解説 を ご覧下さい.
■C++版プログラム(問題C／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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// 解き直し. // https://img.atcoder.jp/data/arc/050/review.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; using vvl = vector<vl>; #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--) // Fermat's little theorem から, 大きな冪乗の計算を行う. // -> 但し, 割る数が, 素数と限らないので, 逆数計算に使用しないこと. // @param a: べき乗したい正整数. // @param b: 指数. // @param m: 割る数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b, LL m){ LL t = 1; while(b){ if(b & 1) t = (t * a) % m; a = a * a % m; b >>= 1; } return t; } // 行列乗算を行う. // @param a: 行列. // @param b: 行列. // @param m: 割る数. // @return: 計算結果(mod版). vvl matrixMultiplication(vvl &a, vvl &b, LL m){ int n = a.size(); vvl ret(n, vl(n, 0LL)); rep(i, n){ rep(j, n){ LL t = 0; rep(k, n){ t += a[i][k] * b[k][j]; t %= m; } ret[i][j] = t; } } return ret; } int main(){ // 1. 入力情報. LL A, B, M; scanf("%lld %lld %lld", &A, &B, &M); // 2. (2, 2)行列のべき乗. auto f = [&](LL b, LL d, LL m) -> vvl{ // 2-1. 返却用行列. vvl t(2, vl(2, 0LL)); rep(i, 2) t[i][i] = 1; // 2-2. 基準とする行列. vvl a(2, vl(2, 0LL)); a[0][0] = mPow(10LL, d, m); a[0][1] = a[1][1] = 1; // 2-3. べき乗計算. while(b){ if(b & 1) t = matrixMultiplication(t, a, m); a = matrixMultiplication(a, a, m); b >>= 1; } // 2-4. 返却. return t; }; // 3. one(A). // -> 解説の漸化式を, 以下のような行列と見る. // | a[k + 1] | = | 10 1 | * | a[k] | // | 1 | | 0 1 | | 1 | // vvl matrixA = f(A - 1, 1LL, M); LL oneA = (matrixA[0][0] + matrixA[0][1]) % M; // 4. one(B) / one(D). // -> 解説の漸化式を, 以下のような行列と見る. // | a[k + 1] | = | (10 の D乗) 1 | * | a[k] | // | 1 | | 0 1 | | 1 | // LL D = __gcd(A, B); vvl matrixBD = f(B / D - 1, D, M); LL oneBD = (matrixBD[0][0] + matrixBD[0][1]) % M; // 5. 出力. printf("%lld\n", oneA * oneBD % M); 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 |
[入力例] 2 3 100 [出力例] 21 ※AtCoderのテストケースより [入力例] 2 2 121 [出力例] 11 ※AtCoderのテストケースより [入力例] 10000000000 1 10007 [出力例] 825 ※AtCoderのテストケースより [入力例] 2 3 2 [出力例] 1 [入力例] 314159265358979323 846264338327950288 197169399 [出力例] 86533291 [入力例] 2100 2230 20160402 [出力例] 149019 [入力例] 2021 1231 2022 [出力例] 989 [入力例] 20210101 20211231 567 [出力例] 237 |
■参照サイト
AtCoder Regular Contest 050