AtCoder Beginer Contest 070 C - Multiple Clocks

　みなさん、おはこんばんにちは。またしても #いいねされた数だけAtCoderでAC タグのための問題です。

　ABC070のC問題「Multiple Clocks(意訳：時計がいっぱい)」です。N個の自然数T[i] (1<=i<=N) がもらえるので、T[1]からT[N]までの最小公倍数を教えてあげる問題です。

#include <iostream>
typedef long long ll;
using namespace std;
 
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b, a%b);
}
 
ll lcm(ll a, ll b){
    ll g = gcd(a, b);
    return (a / g) * b;
}
 
int main(void){
    int N;  cin >> N;
    ll T, ans = 1LL;
    for(int i=0; i<N; i++){
        cin >> T;
        ans = lcm(ans, T);
    }
 
    cout << ans << endl;
 
    return 0;
}

　関数gcdは最大公約数(GCD:greatest common divisor)を返し、関数lcmは最小公倍数(LCM:least common multiple)を返します。gcdでやってるのは、ユークリッドの互除法で、lcmでは、2つの自然数a,bについて、LCM = (a*b)/GCD が成り立つことを使って、オーバーフローしないように計算しています。この中で、gcdを呼び出しています。
　あと、私みたいに次のようにlcmを求めてしまうと、 (a, b)=(1,1e18) とかのとき(2e9=2*10^9)、O(1e18)になってしまって、余裕でTLEになってしまいます。気を付けましょう。

#include <iostream>
typedef long long ll;
using namespace std;

ll a, b;
ll lcm(x, y){
  if(x==y) return x;
  else if(x<y) x += a;
  else if(y<x) y += b;
  return lcm(x,y);
}
//

　なので、ユークリッドの互除法を使います。ユークリッドの互除法なら、O( log(1e18) ) だそうです。つまり、全体でO(Nlog(1e18) < 1e6)なので、余裕です。
　ちなみに、O(1e9) 程度が競プロにおける標準的な(2秒)計算量の制限になります。

　あ、あと、typedef はだいたいdefineみたいな感じだけど、既にある型(int, bool, long long 等)に新しい名前(integer, boolen, ll 等)を与えたいときに使います。

　じゃ、ちゃお。