C++の練習を兼ねて, AtCoder Beginner Contest 179 の 問題E (Sequence Sum) を解いてみた.
■感想.
1. 問題E は, 方針が見えなかったので, 解説を参照して実装して, AC版に到達できた.
※ 余談として, 問題D は, 全く理解が追い付かず, 解説の実装(方針)を, ほぼ丸暗記することにして, 深入りしない(汗).
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト
AtCoder Beginner Contest 179 (E – Sequence Sum 解説)
をご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc179/editorial/115 // 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--) #define pb push_back LL a[101010]; // 数列を保存. int main(){ // 1. 入力情報. LL N, X, M; scanf("%lld %lld %lld", &N, &X, &M); // 2. 数列を計算(繰り返しを確認するまで). set<LL> s; LL cur = X; int idx = 0; rep(i, 101010){ // 繰り返しかを判定. if(!s.count(cur)){ a[i] = cur; s.insert(cur); idx = i; }else{ break; } // 次項計算. cur *= cur; cur %= M; } // 3. 数列を分割. LL bSum = 0, cSum = 0; // 合計. vector<LL> b; // 繰り返し始まるまで. vector<LL> c; // 繰り返し部分. bool f = false; // 繰り返し部分開始フラグ. rep(i, idx + 1){ if(cur == a[i]) f = true; if(f) c.pb(a[i]), cSum += a[i]; else b.pb(a[i]), bSum += a[i]; } // 4. N項目までの和を計算. LL ans = 0, bl = (LL)b.size(), cl = (LL)c.size(); if(N <= bl + cl){ rep(i, (int)N) ans += a[i]; }else{ LL q = (N - bl) / cl, r = (N - bl) % cl; ans += bSum; ans += cSum * q; rep(i, (int)r) ans += c[i]; } // 5. 出力. printf("%lld\n", ans); 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 |
[入力例] 6 2 1001 [出力例] 1369 ※AtCoderテストケースより [入力例] 1000 2 16 [出力例] 6 ※AtCoderテストケースより [入力例] 10000000000 10 99959 [出力例] 492443256176507 ※AtCoderテストケースより [入力例] 10 1 7 [出力例] 10 [入力例] 3 2 1024 [出力例] 22 [入力例] 2020202020 3030 5050 [出力例] 3030 [入力例] 2020202020 3030 50505 [出力例] 56808080744550 [入力例] 3141592653 5897 93238 [出力例] 140770895521631 |
■参照サイト
AtCoder Beginner Contest 179