文系ギャルが0から始める競技プログラミング#21

Intro

この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0

↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#20

・ABC125C

前回コンテスト参加時に意味わからなくて手を付けなかった問題に、
師による天の声とともに挑戦してみます！！！！！

問題文
N個の整数A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を1つ選んで、1以上10^9以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。
書き換えた後のN個の整数の最大公約数の最大値を求めてください。

制約
入力は全て整数である。
2≤N≤10^5
1≤Ai≤10^9

入力
入力は以下の形式で標準入力から与えられる。
NA1A2...AN

出力
書き換えた後のN個の整数の最大公約数の最大値を出力せよ。
― C - GCD on Blackboard

まずは自力で考えます。
好きな整数と書き換えるということは、書き換えたいやつの他の整数たちの最大公約数は変わらないはず。
→消すことと同じ、と考えました。
消したら最大公約数が大きくなるやつをサーチする、ということがこの問題の意図と考えました。（ここまで天才）

が、どうすればいいんだよーーーーーーー！

天の声「再帰ってググってみて」

天の声「またエンジニアジョークが一つ分かるようになったね」

天啓を受け蟻本の107ページを開くと、最大公約数についての記述があります。
ユークリッドの互除法って便利なモノがあるらしいです。（今初めて知った）
これを再帰を使って求めるgcdという関数を作ります。

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

コレを使って、累積GCDを求めます。

テストケースを例に取ると、ぱっとみ７が邪魔してるのは分かる。
でもこれじゃ７が邪魔だってわかんねーぞ…

配列を反転させて逆からも求めます。
７が邪魔してるのはわかった。
さて、どう判定しよう、、、。

int main()
{
   int N;
   cin >> N;
   int first[100000] = {};
   int last[100000] = {};
   int A[100000] = {};
   int a[100000] = {};
   for(int i=0;i<N;i++){
       cin >> A[i];
       a[i] = A[i];
   }
   reverse(a,a+N);
for(int i=0;i<N;i++){
first[i+1] = gcd(A[i],first[i]);
}
for(int i=0;i<N;i++){
last[i+1] = gcd(a[i],last[i]);
}

ここで試行錯誤。ざっと２時間ぐらい悩みます。

ぴこーん（天才ムーブ）

出力用の変数ansを用意します。
前から求めた累積GCDと、後ろから求めた累積GCDの最大公約数のうち、最大のものが答えだと気付きました！！！！
後ろからの場合はマイナス１しておくことで、スタートに立ち返って「いらないものを省いた最大公約数」を実現しています。

   int ans = 0;
   for(int i=0;i<=N;i++){
       ans = max(ans,gcd(first[i],last[N-1-i]));
   }

あとはansを出力して優勝！優勝！

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int gcd(int a,int b){
   if(b==0){
       return a;
   }else{
       return gcd(b,a%b);
   }
}
int main()
{
   int N;
   cin >> N;
   int first[100000] = {};
   int last[100000] = {};
   int A[100000] = {};
   int a[100000] = {};
   for(int i=0;i<N;i++){
       cin >> A[i];
       a[i] = A[i];
   }
   reverse(a,a+N);
for(int i=0;i<N;i++){
first[i+1] = gcd(A[i],first[i]);
}
for(int i=0;i<N;i++){
last[i+1] = gcd(a[i],last[i]);
}
int ans = 0;
   for(int i=0;i<=N;i++){
       ans = max(ans,gcd(first[i],last[N-1-i]));
   }
   cout << ans << endl;
   return 0;
}

てか難しすぎやろ！！！！！！
嘘回答かどうか判別する能力はわたしにはありません。
Twitterやコメントでお待ちしております。

Outro

#22に続く！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。