DDCC本戦2017 B - GCDロボット

• B - GCDロボット

問題概要

N,Z,aiが与えられる。 全てのiについて、gcd(X,a[i])=gcd(Z,a[i])なる最小のXを求めよ。 1<=N<=10⁵,1<=Z,a[i]<=10¹⁸

解法

答えから書くと、lcm_(0<=i<N)(gcd(a[i],Z))。 各iについてgcd(a[i],Z)を求めて、それぞれのlcmを求める。 一応lcmは分割統治でやったけど、そうしなくても大丈夫っぽい。 gcd(a,b)はO(log(max(a,b)))なので、 gcdを求めるのがO(Nlog10¹⁸) lcmを求めるのがO(logN*log10¹⁸)から、 全体でO(Nlog10¹⁸)。

メモ

lcm()について、return a*b/gcd(a,b);と書くとオーバーフローする。 すんなり解けたけど証明はできないな...と思ったので解説を見ると、 ベクトルで考えるといいよ、と書いてあってスッキリ。

以下引用

gcd, lcm 系の操作は、整数を (素因数 2 の個数, 素因数 3 の個数, 素因数 5の個数, ...) という無限次元のベクトルに変換すると見通しがよくなることが多いです。 実は、gcd はこのベクトルの各要素について min を取る操作であり、lcm は max を取る操作です。 つまりこの問題は、あるベクトルの列 ai とベクトル X が与えられ、以下の条件を満すベクトル Z を探せ すべての i, j について、min(Xj ,(ai)j ) = min(Zj ,(ai)j ) という問題になります。 明らかにこの条件はベクトルの各要素に対し独立なので、要素ごとに考えると、結局 Zj = max(min(Xj ,(ai)j )) とすれば良いことがわかります。 よってこの操作を元の整数に戻すと、Z = lcm(gcd(X, ai)) となります。

補足すると各要素(j)について、Zjをmax_(0<=i<N)(min(Xj,(ai)j))よりも小さくすると、あるiについて Zj < min(Xj,(ai)j)となるため矛盾するので、Zj = max(min(Xj,(ai)j))が示せる。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 100005;
const ll lmod = 1e9+7;

int N;
ll Z,a[MAX_N];

ll gcd(ll a,ll b){
  if(a<b) swap(a,b);
  // a >= b
  if(b==0) return a;
  return gcd(b,a%b);
}

ll lcm(ll a,ll b){
  return a/gcd(a,b)*b;
}

ll solve(int l,int r){
  if(abs(r-l)<=1) return a[l];
  else return lcm(solve(l,(l+r)/2),solve((l+r)/2,r));
}

int main(){
  cin >> N >> Z ;
  rep(i,N) scanf("%lld",a+i);
  rep(i,N) a[i] = gcd(Z,a[i]);
  cout << solve(0,N) << endl;
  return 0;
}