C++の練習を兼ねて, AtCoder Beginner Contest 142 の 問題D (D – Disjoint Set of Common Divisors) を解いてみた.
■感想.
1. 解説見る前に, AC版となったので良かったと思う.
本家のサイトABC 142解説をご覧下さい.
■C++版プログラム(問題D／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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; // Efficient program to print all prime factors of a given number // https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/ // 与えられた正整数についての素因数分解を計算. // @param X: 素因数分解を行う整数. // @return ret: 素因数分解 の 結果 を 返却. map<LL, int> div(LL X){ // 1. X を 2で割り切れなくなるまで割っていく. map<LL, int> ret; while(X % 2 == 0) ret[2]++, X >>= 1; // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく. for(LL i = 3; i <= sqrt(X); i += 2){ while(X % i == 0){ ret[i]++; X /= i; } } // 3. X が 2 より 大きな素数であれば, 追加. if(X > 2) ret[X]++; // 4. 本問では, 1 も 追加. ret[1]++; // 5. 出力. return ret; } int main(){ // 1. 入力情報取得. LL a, b; scanf("%lld %lld", &a, &b); // 2. a, b の 最大公約数. LL g = __gcd(a, b); // printf("g=%lld\n", g); // 3. g を 素因数分解. map<LL, int> m = div(g); // for(auto &p : m) printf("%lld ", p.first); // printf("\n"); // 4. 出力 ～ 後処理. printf("%d\n", m.size()); 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 |
[入力例] 12 18 [出力例(debug版)] g=6 1 2 3 3 ※AtCoderテストケースより [入力例] 420 660 [出力例(debug版)] g=60 1 2 3 5 4 ※AtCoderテストケースより [入力例] 1 2019 [出力例(debug版)] g=1 1 1 ※AtCoderテストケースより [入力例] 200560490130 7420738134810 [出力例(debug版)] g=200560490130 1 2 3 5 7 11 13 17 19 23 29 31 12 [入力例] 7420738134810 304250263527210 [出力例(debug版)] g=7420738134810 1 2 3 5 7 11 13 17 19 23 29 31 37 13 [入力例] 13201409035815 171618317465595 [出力例(debug版)] g=13201409035815 1 3 5 7 11 13 17 19 23 29 53 11 |
■参照サイト
AtCoder Beginner Contest 142