AGC018

大爆散☆

http://agc018.contest.atcoder.jp/

AC：Aのみ300点

A

解法：鳩ノ巣応用

全ての数のGCDを取ってKがその数で割り切れればOKなのになんでこんな実装をしたのか自分でもこれが分からない

因みに実行時間1600ms超

#include <iostream>
#include <deque>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
using namespace std;
 
////////////////////////
/* a */
int d[10005];
 
int main(){
  int n,k;
  cin >> n >> k;
  bool f=true;
  int a[n+1],m=0,m2=ATCODER;
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(m<a[i])m=a[i];
    if(a[i]==k)m2=a[i];
  }
  if(m2==k);
  else if(k>m)f=false;
  else{
    for(int i=0;i<n;i++){
      if(!(a[i]%2)){
        d[2]++;
        while(!(a[i]%2))a[i]/=2;
      }
      for(int j=3;j<=a[i]&&j<10005;j+=2){
        if(!(a[i]%j)){
          d[j]++;
          while(!(a[i]%j))a[i]/=j;
        }
      }
    }
    int c = 0;
    for(int i=2;i<10005;i++){
      // cout << d[i] << " ";
      if(d[i]==n&&(k%i)){f=false;break;}
    }
    // cout << endl;
  }
  
  if(f)cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
}

ちゃんとGCDをとるとこう

実行時間50ms

#include <iostream>
#include <deque>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
using namespace std;
 
////////////////////////
/* a */
int d[10005];
 
int gcd(int l,int r){
  int m;
  while(r){
    m = r;
    r = l%r;
    l = m;
  }
  return l;
}
 
int main(){
  int n,k;
  cin >> n >> k;
  int a[n+1],m=0,m2=ATCODER;
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(m<a[i])m=a[i];
    if(a[i]==k)m2=a[i];
  }
  int t=gcd(a[0],a[1]);
  REP2(i,2,n){
    t = gcd(t,a[i]);
  }
  
  if(k<=m&&!(k%t))cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
}