C++で複数個の値に対する最大公約数の求め方

ある数とある数の最大公約数を求めるときにユークリッドの互除法を使い再帰的に求める方法は有名ですが，入力される数が3個以上になったときにどのように求めるのか書いていきます．

まずは，通常のユークリッドの互除法のコードです．

int gcd(int a,int b)
{
 if (b==0) return a;
 return gcd(b,a%b);
}

 このようになります．

次に3以上の場合に対して考えていきましょう．

与えれた数a,b,cの最大公約数は

となります．

 よって，3つ以上になった場合のユークリッド互除法の実装も同様に再帰的に実装すればよく，

>|cpp|

int gcd(int a,int b)
{
 if (b==0) return a;
 return gcd(b,a%b);
}
int main()
{
 if (n == 1) cout << a[0] << endl;
 else{
 el = gcd(a[0],a[1]);
 if (n==2) cout << el << endl;
 else{
 for(int i=2;i<n;i++){
 el = gcd(el,mo[i]);
 }
 cout << el << endl;
 }
}

とすることができます．