C++の練習を兼ねて, AtCoder Beginner Contest 161 の 問題F (F – Division or Substraction) を解いてみた.
■感想.
1. 全く方針が見えなかったものの, 解説を見て, 実装できたので良かったと思う.
2. N が 2 の 場合は, 1 が 正答っぽいので, 注意が必要と思った.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 161 解説をご覧下さい.
■C++版プログラム(問題F／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 |
// 解き直し. // https://img.atcoder.jp/abc161/editorial.pdf #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 #define all(x) x.begin(), x.end() // 与えられた正の整数のすべての約数を抽出. // @param X: 約数を抽出したい正の整数. // @return ret: すべての約数(※2以上). vector<LL> div(LL X){ vector<LL> ret; for(LL d = 2; d * d <= X; d++){ if(X % d == 0){ ret.pb(d); if(d * d != X) ret.pb(X / d); } } // hand_03 で WA版のため, ロジック修正. // ret.pb(X); if(X > 1) ret.pb(X); sort(all(ret)); return ret; } int main(){ // 1. 入力情報. LL N; scanf("%lld", &N); // 2. 解説通り. // 2-1. N - 1 の 約数 を 計算. vector<LL> v1 = div(N - 1); // 2-2. N の 約数 を 計算. vector<LL> v2 = div(N); // 2-3. 割り算を一度も行わない. LL ans = v1.size(); // 2-4. 割り算を一度以上行う場合. for(auto &k : v2){ LL n = N; while(n % k == 0) n /= k; if(n % k == 1) ans++; } // 3. 出力. 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 |
[入力例] 6 [出力例] 3 ※AtCoderテストケースより [入力例] 3141 [出力例] 13 ※AtCoderテストケースより [入力例] 314159265358 [出力例] 9 ※AtCoderテストケースより [入力例] 2 [出力例] 1 [入力例] 271828182845 [出力例] 24 |
■参照サイト
AtCoder Beginner Contest 161