C++の練習を兼ねて, AtCoder Regular Contest 165 の 問題A (Sum equals LCM) を解いてみた.
■感想.
1. 問題A は, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 165 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A/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 |
// 解き直し. // https://atcoder.jp/contests/arc165/editorial/7130 // C++20(GCC 12.2) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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 const int MAX = 31623; int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. 素数. vi a(MAX + 1, 0), v; repx(i, 2, MAX + 1){ if(a[i]) continue; repex(j, i * 2, MAX + 1, i) ++a[j]; } repx(i, 2, MAX + 1) if(!a[i]) v.pb(i); // 3. テストケース. rep(i, T){ // 3-1. 各テストケース. int N; scanf("%d ", &N); // 3-2. N を 割り切る最小の素数は? int p = -1; for(auto &x : v){ if(N % x == 0){ p = x; break; } } // 3-3. N が 素数. if(p == -1){ puts("No"); continue; } // 3-4. N を 素数で割っていく. int n = N, r = 0; while(r == 0){ r = n % p; n /= p; } // 3-5. 出力. puts((n == 0 && r == 1) ? "No" : "Yes"); } 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 |
[入力例] 4 6 4 998244353 367291763 [出力例] Yes No No Yes ※AtCoderのテストケースより [入力例] 10 2 6 10 121 1089 2024 83521 123456 166375 912704521 [出力例] No Yes Yes No Yes Yes No Yes Yes No |
■参照サイト
AtCoder Regular Contest 165