记录编号	346371	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]细胞分裂	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.823 s
提交时间	2016-11-12 08:45:55	内存使用	0.26 MiB

// 设答案为t, 也就是求S ^ t mod m1 ^ m2 = 0 的最小的t
// 唯一分解, S ^ t 变成p1 ^ (a1 * t) * p2 ^ (a2 * t)..., m1 ^ m2变成q1 ^ (b1 * m2) * q2 ^ (b2 * m2)...
// 整除的要求: 唯一分解之后m1的素因子S都有, 并且这些素因子的次数m1 <= S

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;

int p[110], a[110], q[110], b[110];// 记录m1的素因子和次数
int n, m1, m2, S, ans = 0x3f3f3f3f;

inline void Read(int& a)
{
	a = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') {
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

inline void Init(int a)
{
	int m = sqrt(a + 0.5), cnt = 0;
	for (int i = 2; i <= m; ++i) {
		if (a % i == 0) q[++cnt] = i;
		while (a % i == 0) {
			b[cnt]++;
			a /= i;
		}
	}
	if (a > 1) { q[++cnt] = a; b[cnt] = 1; }
	q[0] = cnt;
	for (int i = 1; i <= cnt; ++i)
		b[i] *= m2;
}

inline void Divide(int n)
{
	memset(a, 0, sizeof a);
	memset(p, 0, sizeof p);
	int m = sqrt(n + 0.5), cnt = 0;
	for (int i = 2; i <= m; ++i) {
		if (n % i == 0) p[++cnt] = i;
		while (n % i == 0) {
			a[cnt]++;
			n /= i;
		}
	}
	if (n > 1) { p[++cnt] = n; a[cnt] = 1; }
	p[0] = cnt;
}

inline void Check()
{
	int ret = 0;
	for (int i = 1; i <= q[0]; ++i) {
		int pos = lower_bound(p + 1, p + 1 + p[0], q[i]) - p;// p数组一定是上升的
		if (p[pos] != q[i]) return;// m1的某个素因子没有出现
		ret = max(ret, (int)ceil(1.0 * b[i]/ a[pos]));
	}
	ans = min(ans, ret);
}

#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("cell.in", "r", stdin); freopen("cell.out", "w", stdout);
#endif

	Read(n); Read(m1); Read(m2);
	Init(m1);
	while (n--) {
		Read(S);
		Divide(S);
		Check();
	}
	if (ans == 0x3f3f3f3f) printf("-1\n");
	else printf("%d\n", ans);

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}
/*
【输入输出样例 1】
cell.in
1
2 1
3
cell.out
-1
【输入输出样例1 说明】
经过 1 秒钟，细胞分裂成3 个，经过2 秒钟，细胞分裂成9 个，……，可以看出无论怎么分裂，细胞的个数都是奇数，因此永远不能分入2 个试管。
【输入输出样例 2】
cell.in
2
24 1
30 12
cell.out
2
*/