AGC018 A : Getting Difference(300)
作成日：2017.07.24
最終更新日：2017.07.24
問題概要
$N$個の整数$A_i$の集合に対し、2つの異なる要素の差をその集合に加えることを繰り返す。
それによって、整数$K$が集合の要素となるようにできるか判定せよ。
制約
$1 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$
$1 \leq K \leq 10^9$
考え方
$A_i < K$ならば不可能であることは明らか。
そうでない場合、$1$が集合の要素になっていれば必ず可能であることも明らか。
そこで、$1$が集合の要素になり得ないのはどんなときかを考える。
2つの要素$X,Y$で差を取った後、その差と$min(X,Y)$とまた差を取る、という操作を繰り返すとこれはユークリッドの互除法に他ならない。
よって、$1$が集合の要素になり得ないのは$A_i$の最大公約数が$1$でない時だと分かる。
そして、その場合はKが最大公約数の倍数であるか否かで判定できることも分かる。
また、これらのことは$N=1$のときにも成り立つ。
ソースコード
マクロ等はこちら
int N,K;
int A[100010];
int gcd(int x , int y){
return y == 0 ? x : gcd(y,x%y);
}
int main(){
scanf("%d%d" , &N , &K);
repp(i,0,N){
scanf("%d" , A + i);
}
sort(A,A+N);
if(A[N-1] < K){
printf("IMPOSSIBLE\n");
return 0;
}
int g = A[0];
repp(i,1,N){
g = gcd(z,A[i]);
}
printf("%s\n" , K%g == 0 ? "POSSIBLE" : "IMPOSSIBLE");
return 0;
}解法まとめ
$max(A_i) = A[N-1] < K$の場合は不可能。(14-17行)
そうでない場合は、$A_i$たちの最小公倍数$g$をとって$K = 0 (mod \: g)$かどうかで判定する。(18-22行)