HPU第一次積分賽 E.Max Gcd

• 2020 年 4 月 9 日
• 筆記

E. Max Gcd

單點時限: 2.0 sec 記憶體限制: 512 MB

一個數組a，現在你需要刪除某一項使得它們的gcd最大，求出這個最大值。

輸入格式 第一行輸入一個正整數n，表示數組的大小，接下來一行n個數，第i個數為ai。(2≤n≤105,1≤ai≤109)

輸出格式 輸出刪除掉某個數以後的gcd的最大值。

樣例

input 4 2 4 8 1 outpu| 2

input 4 1 2 3 4

output 1

提示 樣例一：刪除第四個元素後，2,4,8的最大公因子為2。 樣例二：無論刪除哪一個，最大公因子都為1。

這個題剛開始想著直接暴力，後來發現時間不允許就放棄了，賽後我是師父說直接先把數組從前到後依次gcd存在一個數組裡，然後在從後向前依次gcd再放另一個數組裡，然後在直接暴力就行了！

紅線代表從前向後依次gcd，藍線是從後向前。然後一個一個去除保留最大的數據就行！

#include<algorithm>  #include<iostream>    using namespace std;    int a[100100],b[100100],c[100100];    int main()  {      int n;      cin>>n;      cin>>a[1];      b[1]=a[1];      for(int i=2;i<=n;i++)      {          cin>>a[i];          b[i]=__gcd(b[i-1],a[i]);//從前向後依次gcd      }      c[n]=a[n];      for(int i=n-1;i>=1;i--)      {          c[i]=__gcd(c[i+1],a[i]);//從後向前依次gcd      }      int maxn=max(b[n-1],c[2]);//因為防止數組下標越界所以事先比較去掉第一項和                              //去掉最後一項哪個大，保留打的一個      for(int i=2;i<n;i++)      {  //b[i-1]和c[i+1]剛好是第i項之前的所有項的gcd和第i項之後的所有項的gcd          maxn=max(__gcd(b[i-1],c[i+1]),maxn);          //因為一直保留的是最大的值，所以最後的maxn就是答案      }      cout<<maxn<<endl;  }