首页 > 其他分享 >洛谷题单指南-数学基础问题-P1069 [NOIP2009 普及组] 细胞分裂

洛谷题单指南-数学基础问题-P1069 [NOIP2009 普及组] 细胞分裂

时间:2024-04-13 15:12:54浏览次数:28  
标签:m1m2 int 洛谷题 31 NOIP2009 P1069 m1 m2 质因数

原题链接: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

相关文章

  • 洛谷题单指南-数学基础问题-P1072 [NOIP2009 提高组] Hankson 的趣味题
    原题链接:https://www.luogu.com.cn/problem/P1072题意解读:求有多少个x,满足x和a0​的最大公约数是a1​,x和b0​的最小公倍数是b1,多组数据。解题思路:枚举法:因为x和a0​的最大公约数是a1​,x和b0​的最小公倍数是b1,所以x不大于b1​。枚举x有两种思路:1、x是a1的倍数,最多需要枚举......
  • 洛谷题单指南-数学基础问题-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
    原题链接:https://www.luogu.com.cn/problem/P1029题意解读:已知x,y,求有多少对p、q,使得p、q的最大公约数为x,最小公倍数为y。解题思路:枚举法即可。枚举的对象:枚举p,且p必须是x的倍数,还有p<=yq的计算:q=x*y/p,q要存在,必须x*y%p==0,且gcd(p,q)==x100分代码:#include......
  • 洛谷题单指南-数学基础问题-P1835 素数密度
    原题链接:https://www.luogu.com.cn/problem/P1835题意解读:要计算L-R范围内素数的个数。解题思路:直接对L~R的每个数判断素数肯定不可取,因为L、R的范围较大。既然要计算素数的个数,那么可以把其中的合数标记出来即可。如何标记合数?可以借助于筛素数的算法思想,枚举每一个素数,然......
  • 洛谷题单指南-数学基础问题-P3383 【模板】线性筛素数
    原题链接:https://www.luogu.com.cn/problem/P3383题意解读:素数筛模版题。解题思路:素数筛介绍所谓素数(质数),是指除了1和它本身以外不再有其他因数的自然数,一般用试除法判断素数(时间复杂度:O(sqrt(n))):boolisprime(intx){if(x<=1)returnfalse;for(inti=2;i*......
  • 洛谷题单指南-数学基础问题-P2926 [USACO08DEC] Patting Heads S
    原题链接:https://www.luogu.com.cn/problem/P2926题意解读:有n个数,计算每个数能整除其他数的个数。解题思路:a[100005]记录所有的数,h[1000005]记录所有数的个数,cnt[1000005]记录所有数能整除其他数的个数只需要读入a数组,同时更新h[a[i]]++再依次从小到大遍历h的下标每一个数i,如......
  • 洛谷题单指南-数学基础问题-P2638 安全系统
    原题链接:https://www.luogu.com.cn/problem/P2638题意解读:把a个红球、b个黑球放入n个盒子,求所有的方法。解题思路:盒子中可以放也可以不放,可以放任意个,因此,题目可以转化为将i个红球(0<=i<=a),j个黑球(0<=j<=b)放入n个盒子的方案数之和,设f(n,i,j)表示将一个红球、j个黑球放入n......
  • 洛谷题单指南-数学基础问题-P3913 车的攻击
    原题链接:https://www.luogu.com.cn/problem/P3913题意解读:车所在的行、列一共有多个个格子。解题思路:假设3*3的棋盘,有三个车分析得知,三个车覆盖了第1、2两行,第2、3两列,覆盖的格子数用公式计算就是2*3+2*3-2*2=8也就是两行格子数加两列格子数再减去交叉点。因此......
  • C++ [NOIP2009 普及组] 分数线划定
    文章目录一、题目描述[NOIP2009普及组]分数线划定题目描述输入格式输出格式样例#1样例输入#1样例输出#1提示二、参考代码一、题目描述[NOIP2009普及组]分数线划定题目描述世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才,A市对所......
  • 洛谷题单指南-数学基础问题-P2789 直线交点数
    原题链接:https://www.luogu.com.cn/problem/P2789题意解读:n条直线可以形成不同交点数的方案数。解题思路:对于n=1、2、3、4的情况进行模拟:n=1时,有1种不同的交点数n=2时,有2种不同的交点数n=3时,有3种不同的交点数n=4时,有5种不同的交点数对n=4的情况,分情况讨......
  • 洛谷题单指南-数学基础问题-P1866 编号
    原题链接:https://www.luogu.com.cn/problem/P1866题意解读:N个整数M1~Mn,对每个整数Mi,选取1~Mi之间的一个数,使得N个数都不一样的选法。解题思路:将M1~Mn由小到大排序,第1个的选法有M1种第2个的选法有M2-1种第3个的选法有M3-2种......第n个选法有Mn-n+1种全部相乘取模即可。......