原题链接:https://www.luogu.com.cn/problem/P1069
题意解读:一个数s代表细胞经过一天分裂的个数,则经过t天后个数为st,要计算经过几天后能整除m1m2,也就是st % m1m2 == 0,有多个s,要计算天数最少就可以满足条件的。
解题思路:
直接求st % m1m2显然不可取,会超出整数最大范围,高精度也不是好办法。
对于这种情况,可以分解质因数
以样例2为例:
m1 = 24, m2 = 1,m1m2 = 23*31
s = 30时,st = (21*31*51)t = 2t*3t*5t,要能整除m1m2 = 23*31, 2t>=23, 3t>=31, t至少是3,也就是max(3/1, 1/1)
s = 12时,st = (22*31)t = 22t*3t,要能整除m1m2 = 23*31,22t>=23,3t>=31, t至少是2,也就是max(⌈3/2⌉,1/1),注意3/2上取整
再看样例1:
m1 = 2, m2 = 1, m1m2 = 21
s = 3时,st = 31,由于m1m2 = 21的质因数中有2,而s的质因数中没有2,所以st永远也不可能整除21
根据上面的分析,解法就比较明确了:
1、对m1^m2分解质因数,主要是对m1分解质因数,m2乘上各个质因数的指数,作为最终的指数即可
质因数用vector<int> pm保存,对应的指数用vector<int> px保存。
2、再对每一个s进行处理,同样对s分解质因数,这次用hash数组保存int ps[30005],
因为m1最大30000,其质因数也不超过30000,因此s的质因数超过30000的不必要关心,只看跟m1一致的质因数即可。
ps[i] = cnt存的是s的质因数i的指数为cnt。
3、对m1^m2的每一个质因数,去s的质因数里找,
如果找不到,说明s^t永远也无法整除m1^m2;
如果能找到,就计算res = ⌈m1^m2的指数 / s的指数⌉ ,找res最大的就是改s经过多少天能整除m1^m2
4、对求得的多个res,取最小值
5、如果每个s都无法整除m1^m2,则输出-1
100分代码:
#include <bits/stdc++.h>
using namespace std;
int n, m1, m2;
int s;
vector<int> pm; //m1^m2的质因数
vector<int> px; //prims里每个质因数的指数
int ps[30005]; //s的质因数对应的指数
int ans = INT_MAX;
int main()
{
cin >> n >> m1 >> m2;
//对m1^m2分解质因数
for(int i = 2; i * i <= m1; i++)
{
if(m1 % i == 0)
{
int cnt = 0;
while(m1 % i == 0)
{
cnt++;
m1 /= i;
}
pm.push_back(i);
px.push_back(cnt * m2);
}
}
if(m1 > 1)
{
pm.push_back(m1);
px.push_back(m2);
}
for(int i = 1; i <= n; i++)
{
cin >> s;
//对每一个s分解质因数,不考虑超过m1的质因数
memset(ps, 0, sizeof(ps));
for(int j = 2; j * j <= s && j <= 30000; j++)
{
if(s % j == 0)
{
int cnt = 0;
while(s % j == 0)
{
cnt++;
s /= j;
}
ps[j] = cnt;
}
}
if(s > 1 && s <= 30000) ps[s] = 1;
int res = 0; //如果m1=1,只需要0天就可以乘除1
bool success = true;
//检查m1的每个质因数
//如果有质因数在s的质因数中不存在,表示不能满足要求
//如果质因数都存在,计算m1的质因数指数 / s的中相同质因数指数,向上取整,最大的结果即需要的时间
for(int j = 0; j < pm.size(); j++)
{
if(ps[pm[j]] == 0) //如果有m1的质因数在s中不存在
{
success = false;
break;
}
else
{
int low = ps[pm[j]];
int high = px[j];
int cnt = high / low;
if(high % low != 0) cnt++;
res = max(res, cnt); //找每个质因数要增长天数最大的一个
}
}
if(success) ans = min(ans, res); //多个时间取最小值
}
if(ans == INT_MAX) cout << -1;
else cout << ans << endl;
return 0;
}
标签:m1m2,int,洛谷题,31,NOIP2009,P1069,m1,m2,质因数 From: https://www.cnblogs.com/jcwy/p/18132878