记录编号	399684	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]细胞分裂	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.138 s
提交时间	2017-04-27 13:02:40	内存使用	0.54 MiB

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <list>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
using namespace std;
const int MAXN = 50000;
int pm[MAXN], tot;
bool vis[MAXN];
void pre(){
  for(int i = 2; i <= MAXN; i++){
    if(!vis[i])pm[tot++] = i;
    for(int j = 0; j < tot; j++){
      int k = pm[j]*i; if(k > MAXN)break;
      vis[k] = true;
      if(i%pm[j] == 0)break;
    }
  }
}
typedef vector<pair<int, int> > divinfo;
divinfo divide(int n, int k = 1){
  int m = (int)sqrt(n+0.5);
  divinfo res;
  for(int i = 0; pm[i] <= m; i++){
    int p = pm[i];
    if(n%p == 0){
      int c = 0;
      while(n%p == 0){
        c++;
        n /= p;
      }
      res.push_back(make_pair(p, c*k));
    }
  }
  if(n > 1)res.push_back(make_pair(n, k));
  return res;
}
bool cmp(pair<int, int> a, pair<int, int> b){
  return a.first < b.first;
}
int main(){
  freopen("cell.in", "r", stdin);
  freopen("cell.out", "w", stdout);
  pre();
  int m1, m2, n; scanf("%d %d %d", &n, &m1, &m2);
  divinfo m = divide(m1, m2);
  int ans = 0x7fffffff;
  while(n--){
    int val; scanf("%d", &val);
    divinfo s = divide(val);
    int tmp = 0;
    bool flag = true;
    for(int i = 0; i < m.size(); i++){
      int p = lower_bound(s.begin(), s.end(), m[i], cmp) - s.begin();
      if(p >= s.size() || s[p].first != m[i].first){
        flag = false; 
        break;
      }      
      tmp = max(tmp, (int)ceil(1.0*m[i].second/s[p].second));
    }
    if(flag)ans = min(ans, tmp);
  }
  if(ans != 0x7fffffff)printf("%d\n", ans);
  else puts("-1");
  return 0;
}