AcWing 439. 细胞分裂
原题链接
中等
作者:
蹲在街角〆仰望晴天ゞ
,
2024-04-09 15:22:00
,
所有人可见
,
阅读 4
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10010, INF = 1e9;
int n, m1, m2;
int primes[N], cnt;
bool st[N];
struct node
{
int val, cnt;
} a[N], b[N];
int c[N];
void init()
{
for (int i = 2; i < N; i++)
{
if (!st[i])
{
primes[cnt++] = i;
}
for (int j = 0; primes[j] < N / i; j++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0)
break;
}
}
}
int main()
{
init();
cin >> n >> m1 >> m2;
if (m1 == 1)
{
cout << 0 << endl;
return 0;
}
int idx = 0;
for (int i = 0; i < cnt && primes[i] <= m1; i++)
{
if (m1 % primes[i] == 0)
{
int s = 0;
while (m1 % primes[i] == 0)
s++, m1 /= primes[i];
a[idx++] = {primes[i], s * m2};
}
}
//
int res = INF;
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = 1; i <= n; i++)
{
// 假设这个数符合要求
bool flag = true;
for (int k = 0; k < idx; k++)
if (c[i] % a[k].val != 0)
{
flag = false;
break;
}
if (!flag)
continue;
for (int k = 0; k < idx; k++)
{
int s = 0, t = c[i];
while (t % a[k].val == 0)
s++, t /= a[k].val;
b[k] = {a[k].val, s};
}
// 开始判断条件
int k = 1;
while (true)
{
bool flag = true;
for (int u = 0; u < idx; u++)
{
if (b[u].cnt * k < a[u].cnt)
{
flag = false;
break;
}
}
if (flag)
{
res = min(res, k);
break;
}
k++;
}
}
if (res == 1e9)
res = -1;
cout << res << endl;
return 0;
}