競プロ記録

問題を解いた際に自分の復習用として使ってます

AGC018 A問題

問題

agc018.contest.atcoder.jp

解説

この問題はユークリッドの互除法を用います。ではなぜユークリッドの互除法と言う考え方が出てくるのか解説します。 まずユークリッドの互除法に関して以下のページを読んでください。

math.nakaken88.com

a(modG)が0, b(modG)が0,ならば a-b(modG)も0になることが理解できたかと思います。すると任意の二つの数に関する最大公約数 が書かれたボールを入れることができるため、それらの最大公約数が書かれたボールに対して再び上記の捜査を繰り返すとすべての数の最大公約数が書かれたボールを入れることができます。その最大公約数をGとし、K-G、 K-2G, K-3G,....2G, Gのボールを入れることができるためKがGで割り切れる時、K=x*GであるKのボールも入れることができます。 したがってKがGで割り切れるかどうかを判定すれば良いです。

コード

include

include

include

using namespace std;

int gcd(int a, int b){ if(a%b == 0){ return b; }else{ return gcd(b,a%b); } } int main(void){ int n, k, a[100005]; cin >> n >> k; for(int i=0;i<n;i++){ cin >> a[i]; if(a[i] == k){ cout << "POSSIBLE" << endl; return 0; } } sort(a,a+n); if(a[n-1] < k){ cout << "IMPOSSIBLE" << endl; return 0; } int G = gcd(a[0], a[1]); for(int i=2; i<n; i++){ G = gcd(a[i], G); } if(k%G == 0){ cout << "POSSIBLE" << endl; }else{ cout << "IMPOSSIBLE" << endl; }

return 0;

}