C++の練習を兼ねて, AtCoder Beginner Contest 070 の 問題C(Multiple Clocks)を解いてみた.
■感想.
1. 最小公倍数を計算するときの計算順序で, 途中躓いたが, 計算順序を変えてみる方法に気付いたので, ACとなった.
2. コーディング後, 解説を見たら, おおよそ同じ方針だったので, まずまずの結果だったと思う.
本家のサイトABC 070 解説をご覧下さい.
■C++版プログラム.
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 |
#include <iostream> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) typedef long long LL; // 最大公約数を計算. // https://cs.stackexchange.com/questions/1447/what-is-most-efficient-for-gcd LL gcd (LL a, LL b) { while(b) b ^= a ^= b ^= a %= b; return a; } int main() { // 1. 入力情報取得. LL N; cin >> N; // 2. T1 ~ TN までの最小公倍数を計算. LL LCM; cin >> LCM; FOR(i, 0, N - 1) { LL ti; cin >> ti; // 2-1. 最大公約数計算. LL GCD = gcd(LCM, ti); // 2-2. 最小公倍数更新(改善前). // -> -4927149226598858752 などと, おかしな値が出力されるケースがあったため, コメントアウト. // LCM = LCM * ti / GCD; // 2-3. 最小公倍数更新(改善後). // 入力値 ÷ 最大公約数 を先に計算してから, 最小公倍数 を算出させるように計算順序を変更. LL tigcd = ti / GCD; LCM *= tigcd; } // 3. 出力 ~ 後処理. cout << LCM << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 070
What is most efficient for GCD?