LiveArchive 6582 : UVa 1642 : Magical GCD
問題リンク: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; }