- lizexuan's blog
NOIP2009 细胞分裂
- 2023-11-10 18:12:43 @
题目:
题目解析
先看题目,肥肠的长,但是我们简化后就是设是最小的使得的整数(也有可能不存在),求
虽说关键数字大的吓人但是你先别急
先介绍一个
推论
给定,而 是 的约数的充要条件是,,,即 中每一个质数的幂次都不超过 的。
因此,每个质因子上的幂次直接决定了两数之间的整除性。
例如 , , 看到 的质因子上的幂次都对应的比 小, 便可以在进行取模运算的情况下给出 的结论
有了推论的铺垫,这道题的突破口也是很明显的:
如果, 那么。接下来只需要解决题意中的 的求解。
由推论可以得到, 若中的每个质因子的幂次都比 小时,成立。 中的质因子是否出现由 决定,而质因子出现了几次主要由 决定。若 ( 到 表示与 无关的质因子),那么
应该使得 的 ,满足
所以从 中的每个质因子 出发: 如果这个 不能整除 ,则说明 不包含 这个质因子,进而找不到题设所要求的;如果这个 能整除 ,那么只需要求出对应的,就能算出第 个质因子, 要求 不小于 ,在对所有的这样的要求取最大值,就都得到了 。最后对所有合法的 取最小值就是答案
代码
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> pri;
int m1, m2, n, ans = 2147483647, x;
void fenjie (int a) {
for (int i = 2; i <= sqrt(a); i++) {
if(a % i == 0) {
pri[i]++;
a /= i;
i--;
}
}
if(a > 1) {
pri[a]++;
}
}
int main() {
cin >> n >> m1 >> m2;
fenjie(m1);
while(n--) {
cin >> x;
int res = 0;
for (pair<int, int> p : pri) {
int t = p.first;
if(x % t != 0) {
res = -1;
break;
} else {
int cnt = 0;
for(; x % t == 0; x /= t) {
cnt++;
}
res = max(res, (int)ceil(m2 * 1.0 * p.second / cnt));
}
}
if(res >= 0) {
ans = min(ans, res);
}
}
if (ans >= 2147483647) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}