ABC070-C Multiple Clocks を解いてみた

70回のC問題は完全に数学でしたね．数学の知識を知っていれば解ける問題で，知らなければ解けないだろうなという感触でした． では，以下問題

問題

Multiple Clocks

問題文

N 台の時計があり、i(1≦i≦N) 番目の時計の針はちょうど Ti 秒で時計盤を 1 周します。 最初、全ての時計の針は真っ直ぐ上に向いており、止まっています。 イルカは、全ての時計の針を同時に動かし始めました。 再び、全ての時計の針が真っ直ぐ上に向くのは何秒後でしょうか?

制約

* 1 ≦ N ≦ 100

* 1 ≦ Ti ≦10^18

* 入力は全て整数である。

* 答えは 10^18秒以内である。

---

とこんな感じですね．

色々小難しいことを書いていますが，結論をいうと入力される値の最小公倍数を求めなさいという問題です． 最小公倍数を求める際に最大公約数を求める必要があります．それを求めるアルゴリズムとしてユークリッド互除法があるのでそれを使用します．

考えたこと

ユークリッド互除法を実装するには再帰関数を使えばすごく楽なのでそれを実装すればいいと考えました．

ユークリッド互除法

f(x,y) = x (y == 0) || f(x,x % y) (y != 0)

の関数式になります．

これを実装しますと以下のようになります．

long long dev(long long base,long long num){
    if (num == 0){
        return base;
    } else {
        return dev(num,base % num);
    }
    return base;
}

あとは入力を受け取り，i ~ Nまで繰り返し処理をしながら最小公倍数を探すということをすれば問題は解けます

フロー

• 入力を受け取り
• 答えを 1 に設定する
• 受け取った要素に対して以下の処理を繰り返す
  • もしその要素の剰余が0の場合
    • 答えを答えとその要素の最大にする
  • それ以外の場合以下の処理をする
    • その要素と答えを比べて大小を決める
    • 答えに 大きいほう / 最大公約数 * 小さい方にする
• 答えを出力

プログラム

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;


long long dev(long long base,long long num){
    if (num == 0){
        return base;
    } else {
        return dev(num,base % num);
    }
    return base;
}

int main(void){
    int N;
    cin >> N;
    vector<unsigned long long> T(N);

    for(int i = 0;i < N;i++){
        cin >> T[i];
    }
    unsigned long long ans = 1;
    for(int i = 0;i < N;i++){
        if(ans % T[i] == 0 || T[i] % ans == 0){
            ans = max(ans, T[i]);
        } else {
            // 互除法
            long long hi,low;
            hi = max(ans,T[i]);
            low = min(ans,T[i]);
            ans = hi / dev(hi,low) * low;
        }
    }
    cout << ans << endl;
    return 0;
}

これでAC取れました