记录编号	42360	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]细胞分裂	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.039 s
提交时间	2012-09-20 16:44:34	内存使用	0.63 MiB

#include <cstdio>
const int N = 30000 + 10, INF = 0x7fffff;
int n, m1, m2, s = INF;
int a[N], b[N], m[N];
void sosu(int n) {
    for(int i=2; i<=n; i++) {
        while(n % i == 0) {
            n /= i;
            m[i]++;
        } m[i] *= m2;
    }
}
void tens(int n, int o) {
    int d = 0, t;
    b[o] = 0;
    for(int i=1; i<=m1; i++) if(m[i]) {
        for(d = 0; n % i == 0; d++)
            n /= i;
        if(!d) { b[o] = -1; return; }
        t = m[i] / d + (m[i] % d ? 1 : 0);
        if(t > b[o]) b[o] = t;
    }
}
int main() {
    freopen("cell.in", "r", stdin);
    freopen("cell.out", "w", stdout);
    scanf("%d", &n);
    scanf("%d %d", &m1, &m2);
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
    if(m1 == 1)
        printf("%d\n", 0);
    else {
        sosu(m1);
        for(int i=1; i<=n; i++)
            tens(a[i], i);
        for(int i=1; i<=n; i++)
            if(b[i] > 0 && b[i] < s) s = b[i];
        printf("%d\n", s == INF ? -1 : s);
    }
    return 0;
}