典型的アルゴリズムについて(1)

前置き

この記事はまたまた！ぴょこりんクラスタ Advent Calendar 2017 - Adventarのために書かれたものです。ちなみにこのACが何なのかについては、ぴょこりんクラスタ Advent Calendar is 何？ - ぴょこりんブログが詳しいです。

なにをするか

書くことに困ったので、最近解いた競技プログラミングの問題で必要となったアルゴリズムについて述べる。なお著者のレベルは、Atcoderの300点問題について「実装やるだけ問題」なら大体解ける、特定のアルゴリズムを使うものは怪しい、という感じ。400点以上はまず時間内では解けない。
いくつか候補はあったが、気力の問題で１つだけ。。

最大公約数、最小公倍数

C - Multiple Clocks

入力N個の最小公倍数を返せばよいというのはすぐにわかるけど、どうすればいいんだーと。以下を使う。証明はなし。

• ２個の数に対する最大公約数については、ユークリッドの互除法で算出できる。正整数について、の最大公約数は(はをで割ったときの剰余)に等しい。
• の最小公倍数について、が成立する。なので、最大公約数を求めれば、最小公倍数は求まる。
• ３個以上の数についてなので、前から順に求めればOK

ということで、回答はこんな感じ。LCMを求めるときに先にa,bの乗算するとオーバーフローするので注意（分母は最大公約数であり必ずaを割り切るので、先に割ってOK）。

    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <map>
    #include <numeric>
    #include <set>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <cmath>
    using namespace std;
     
    #define FOR(i,s,e) for (int i = int(s); i < int(e); i++)
    #define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
    #define ISEQ(c) (c).begin(), (c).end()
     
    long long int gcd(long long int a,long long int b){
    	long long int p;
    	if (b > a){
    		p = a;
    		a = b;
    		b = p;
    	}
    	while(b != 0){
    		p = a % b;
    		a = b;
    		b = p;
    	}
    	return a;
    }
     
    long long int lcm(long long int a,long long int b){
    	long long int p = gcd(a,b);
    	long long int ret = a / p * b;
    	return ret;
    }
     
     
    int main(){
    	int N;
    	cin >> N;
    	long long int p[N];
    	FOR(i,0,N){
    		cin >> p[i];
    	}
     
    	long long int ret = p[0];
    	FOR(i,1,N){
    		ret = lcm(ret,p[i]);
    	}
     
    	cout << ret << endl;
    	return 0;
    }

おわり

• 数式かくのめんどい。
• 2があるかは知らない。