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