从大到小排序,相邻两项作差,求gcd,如果K是gcd的倍数并且K<=max{a(i)},必然有解,否则无解。

可以自己手画画证明。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,K,a[100010];
int main(){
scanf("%d%d",&n,&K);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
if(n==1){
if(K==a[1]){
puts("POSSIBLE");
}
else{
puts("IMPOSSIBLE");
}
return 0;
}
sort(a+1,a+n+1);
int GCD=a[1];
for(int i=2;i<=n;++i){
GCD=__gcd(GCD,a[i]-a[i-1]);
}
if(K<=a[n] && K%GCD==0){
puts("POSSIBLE");
}
else{
puts("IMPOSSIBLE");
}
return 0;
}
05-27 20:12