読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

LiveArchive 6582 : UVa 1642 : Magical GCD

UVa LiveArchive 苦手分野 数学

問題リンク:https://icpcarchive.ecs.baylor.edu/external/65/6582.pdf

問題概要:
長さn(1<= n <= 100000)の数列が与えられる
数列の各要素a[i]は1以上10^12以下
数列の連続した部分列を取り出し、(部分列全体のgcd) * (部分列の長さ) を値とする
値の最大値を出力せよ

解法:
部分列の最も右となる要素を全探索する
最も右の要素の番号をiとする
iを0からn−1まで順に試す
その中で[j,i] (0<=j<=i)から得られる各gcdについての値を求める
gcdが重複しているものについては最もjが0に近いようなものを選ぶ
このとき、[j,i]から得られるgcdの集合の大きさはO( log(a[i]) )しかない
なぜなら、
gcd(a[j,i-1]) != gcd(a[j,i]) のとき、gcd(a[j,i-1])/2>=gcd(a[j,i])なので、
gcd(a[j,i])はO(log(a[i])回後には1になるため

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

int main() {
  int T;
  cin >> T;
  while( T-- ) {
    int n;
    cin >> n;
    ll maxi = 0;
    map<ll,int> mp; 
    rep(i,n) {
      ll a;
      cin >> a;
      maxi = max(maxi,a);
      map<ll,int> tmp;
      tmp[a] = i;
      for(map<ll,int>::iterator it=mp.begin();it!=mp.end();it++) {
	ll gcd = __gcd(it->first,a);
	maxi = max(maxi,gcd*(ll)(i-(it->second)+1));
	if( tmp.count(gcd) ) tmp[gcd] = min(tmp[gcd],it->second);
	else                 tmp[gcd] = it->second;
      }
      mp = tmp;
    }
    cout << maxi << endl;
  }
  return 0;
}