信息学奥赛一本通 1947：【09NOIP普及组】细胞分裂 | 洛谷 P1069 [NOIP2009 普及组] 细胞分裂

ybt 1947：【09NOIP普及组】细胞分裂
洛谷 P1069 [NOIP2009 普及组] 细胞分裂

每个整数x都可以进行质因数分解，写成公式为 x = p 1 a 1 p 2 a 2 . . . p n a n x = p_1^{a_1}p_2^{a_2}...p_n^{a_n} x=p1a1​​p2a2​​...pnan​​，其中 p 1 ∼ p n p_1sim p_n p1​∼pn​都为s的质因数。

本题可以抽象为：有数字 s 1 , s 2 , . . . , s n s_1,s_2,...,s_n s1​,s2​,...,sn​，s指其中的某个数字。看在这个数字序列中，哪个个数字 s j s_j sj​的幂 s j i s_j^i sji​能整除 m 1 m 2 m_1^{m_2} m1m2​​，且幂指数最小。
根据质因数分解公式 x = p 1 a 1 p 2 a 2 . . . p n a n x = p_1^{a_1}p_2^{a_2}...p_n^{a_n} x=p1a1​​p2a2​​...pnan​​，我们可以设计一个表示幂指数的结构，里面包含底数与指数。
将 m 1 m_1 m1​分解质因数，得到 m 1 = p 1 a 1 p 2 a 2 . . . p u a u m_1 = p_1^{a_1}p_2^{a_2}...p_u^{a_u} m1​=p1a1​​p2a2​​...puau​​，
那么 m 1 m 2 = ( p 1 a 1 p 2 a 2 . . . p u a u ) m 2 = p 1 a 1 m 2 p 2 a 2 m 2 . . . p u a u m 2 m_1^{m_2}=(p_1^{a_1}p_2^{a_2}...p_u^{a_u})^{m_2}=p_1^{a_1m_2}p_2^{a_2m_2}...p_u^{a_um_2} m1m2​​=(p1a1​​p2a2​​...puau​​)m2​=p1a1​m2​​p2a2​m2​​...puau​m2​​
将每个s都分解质因数，得到 s j = q 1 b 1 q 2 b 2 . . . q t b t s_j = q_1^{b_1}q_2^{b_2}...q_t^{b_t} sj​=q1b1​​q2b2​​...qtbt​​

如果 s j i s_j^i sji​能整除 m 1 m 2 m_1^{m_2} m1m2​​，那么 s j s_j sj​的质因数必须包含 m 1 m_1 m1​的所有质因数。
在分解 m 1 m_1 m1​的质因数的同时，将 m 1 m_1 m1​的所有质因数的1次方乘积，得到数字 m 0 m_0 m0​。如果 s j s_j sj​包含 m 1 m_1 m1​的所有质因数，那么 s j s_j sj​一定可以整除 m 0 m_0 m0​
如果每个 s j s_j sj​的质因数都不能包含 m 1 m_1 m1​的所有质因数，则输出-1。

接下来求 s j s_j sj​的指数i：
对于 m 1 m_1 m1​中的每个质因数 p k p_k pk​，它在m1中的指数为 a k a_k ak​，那么在 m 1 m 2 m_1^{m_2} m1m2​​中 p k p_k pk​的指数为 a k m 2 a_km_2 ak​m2​，在 s j s_j sj​中 p k p_k pk​的指数为 b k b_k bk​，那么 s j i s_j^i sji​中 p k p_k pk​的指数为 i ⋅ b k icdot b_k i⋅bk​。要想让 s j i s_j^i sji​能整除 m 1 m 2 m_1^{m_2} m1m2​​，必须有 i ⋅ b k ≥ a k m 2 icdot b_k ge a_km_2 i⋅bk​≥ak​m2​，所以 i ≥ a k m 2 b k i ge frac{a_km_2}{b_k} i≥bk​ak​m2​​，i最小为 ⌈ a k m 2 b k ⌉ lceil frac{a_km_2}{b_k} rceil ⌈bk​ak​m2​​⌉。
遍历所有可能的k，求 ⌈ a k m 2 b k ⌉ lceil frac{a_km_2}{b_k} rceil ⌈bk​ak​m2​​⌉的最大值，即为能使 s j i s_j^i sji​整除 m 1 m 2 m_1^{m_2} m1m2​​的i的最小值。
对每个 s j s_j sj​都求出其对应的能使 s j i s_j^i sji​整除 m 1 m 2 m_1^{m_2} m1m2​​的i的最小值，比较得到其中i的最小值，即为问题的结果。

特殊地，如果 m 1 m_1 m1​是1，那么任何1个细胞在0秒后都有1个，是符合要求的，输出0。

#include 
using namespace std;
#define N 10005
#define INF 0x3f3f3f3f
struct Pow
{
    int b, i;//b底数，i指数  
    Pow(){}
    Pow(int x, int y):b(x),i(y){}
};
int n, m1, m2, m0 = 1, s[N], mini = INF;
vector v_m;
void initVM()
{
    int a = 2, x = m1;
    while(a <= x)
    {
        if(x % a == 0)
        {
            if(v_m.empty() == false && v_m.back().b == a)
                v_m.back().i++;
            else
                v_m.push_back(Pow(a,1));
            x /= a;
        }
        else
            a++;
    }
    for(i = 0; i < v_m.size(); ++i)
    {
        m0 *= v_m[i].b;//所有m1的质因子的一次方的乘积 
        v_m[i].i *= m2;//m的所有质数乘m2 
    }
}
int main()
{
    cin >> n >> m1 >> m2;
    for(int i = 1; i <= n; ++i)
        cin >> s[i];
    if(m1 == 1)//任何细胞0秒时都有1个 
    {
        cout << 0;
        return 0;
    }
    initVM();
    for(int j = 1; j <= n; ++j)
    {
        if(s[j] % m0 != 0)//s[i]不包含m1中的某些质因子 
            continue;
        int mxi = 0;//m的质因子个数除s[j]的质因子个数（向上取整）得到的最大倍数 
        for(int i = 0; i < v_m.size(); ++i)
        {
            int a = s[j], k = 0;//s[j]中包含k个v_m[i].b 
            while(a % v_m[i].b == 0)
            {
                a /= v_m[i].b;
                k++;
            }
            mxi = max(mxi, (int)ceil((double)v_m[i].i/k));
        }
        mini = min(mini, mxi);
    }
    if(mini == INF)
        cout << -1;
    else
        cout << mini;
    return 0;
}

#include 
using namespace std;
#define N 10005
#define INF 0x3f3f3f3f
int s[N], n, m1, m2, m0 = 1, mini = INF, m_b[N], m_i[N], mn;//m_b[i]:m的第i个质因数，m_i[i]:m的第i个质数因数的指数  mn:个数 
int main()
{
    int a, x, k, mxi;
    cin >> n >> m1 >> m2;
    for(int i = 1; i <= n; ++i)
        cin >> s[i];
    if(m1 == 1)//任何细胞0秒时都有1个 
    {
        cout << 0;
        return 0;
    }
    a = 2, x = m1;//对m做质因数分解 
    while(a <= x)
    {
        if(x % a == 0)
        {
            if(m_b[mn] == a)
                m_i[mn]++;
            else
            {
                m_i[mn] *= m2;//m的所有质数乘m2         
                m_b[++mn] = a;
                m_i[mn] = 1;
                m0 *= a;//所有m1的质因子的一次方的乘积 
            }
            x /= a;
        }
        else
            a++;
    }
    m_i[mn] *= m2;
    for(int j = 1; j <= n; ++j)
    {
        if(s[j] % m0 != 0)//s[i]不包含m1中的某些质因子 
            continue;
        mxi = 0;//m的质因子个数除s[j]的质因子个数（向上取整）得到的最大倍数 
        for(int i = 1; i <= mn; ++i)
        {
            a = s[j], k = 0;//s[j]中包含k个v_m[i].b 
            while(a % m_b[i] == 0)
            {
                a /= m_b[i];
                k++;
            }
            mxi = max(mxi, (int)ceil((double)m_i[i]/k));
        }
        mini = min(mini, mxi);
    }
    cout << (mini == INF ? -1 : mini);
    return 0;
}