ABC070C - Multiple Clocks

6272 ワード
GCD ABC070C LCM ユークリッドの互除法 GCD テキストリンク

つまり与えられたN個の整数の最小公倍数を求めればいい問題なので、最大の整数を選んで、それを整数倍していき、その他の入力された整数で割り切れる最小の整数を出力すればいいと思ったが、そうは問屋が卸さなかった。

ABC070Ca.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
 int n;
 cin >> n;
 vector<long long> clock(n);
  long long nmax=0;
  for(int i=0;i<n;i++){
    cin >> clock[i];
    nmax=max(clock[i],nmax);
  }
  long long m;
  for(long long i=1;m<1000000000000000000;i++){
    m=i*nmax;
    bool ok=true;
    for(int j=0;j<n;j++){
      if(m%clock[j]!=0)ok=false;
    }

    if(ok){
    break;
    }
  }
  cout << m << endl;//これだと計算量がO(NA)なので当然間に合わない。
}

最大公倍数(lcm)、最小公約数(gcd)が絡んでくる問題はユークリッドの互除法を用いればいい。
まずgcdを求める関数を以下のように求める。

gcd.cpp
ll gcd(ll a,ll b){ //ユークリッドの互除法で最大公約数を求める
  if(b==0) return a;
  return gcd(b,a%b);
}

ユークリッドの互除法について　
https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95

次にgcdからlcmを求める

lcm.cpp
ll lcm(ll a,ll b){//a*b=lcm(a,b)*gcd(a,b)の関係式からa,bのlcm最小公倍数が求まる。
    ll g=gcd(a,b);
  return a/g*b;//a*b/gとすると間違った答えが出力される。
}