P1069 [NOIP2009 普及组] 细胞分裂

题意:

求$S_i^k$ $|$ $m1^{m2}$ 时 $k_{min}$

思路:

由于$m1^{m2}$太大，我们可以提前分解它的质因数
设$m1=pri_1 * j_1+pri_2 * j_2 +\cdots +pri_n * j_n$
则$m1^{m2}=pri_1 * j_1*m2+pri_2 * j_2 *m2+\cdots +pri_n * j_n*m2$
因此$m1^{m2}$的质因数分解只需要在$m1$的基础上给每项的系数乘$m1$ 最后再对每个$S_i$作质因数分解判断即可

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 10005;
const int INF = 2e9;
int n, m1, m2, ans = INF;
int a[N];
int pri[30005], _cnt[30005], tot;
int cnt[30005];
bitset<30005> p;
inline void getPrimes(int n, int t)
{
    p.set();
    p[0] = p[1] = false;
    for (int i = 2; i <= n; i++)
    {
        if (p[i])
        {
            pri[++tot] = i;
            while (t % i == 0)
            {
                t /= i;
                cnt[i] += m2;
            }
        }
        for (int j = 1; j <= tot && i * pri[j] <= n; j++)
        {
            p[i * pri[j]] = false;
            if (i % pri[j] == 0)
                break;
        }
    }
}
inline void getPrimeFac(int x)
{
    int t = a[x];
    for (int i = 1; i <= tot; i++)
    {
        _cnt[pri[i]] = 0;
        while (t % pri[i] == 0)
        {
            t /= pri[i];
            _cnt[pri[i]]++;
        }
    }
}
inline int solve()
{
    int res = -1;
    for (int i = 1; i <= tot; i++)
    {
        int now = pri[i];
        if (!cnt[now])
            continue;
        if (cnt[now] && !_cnt[now])
            return INF;
        res = max(res, (cnt[now] % _cnt[now] == 0 ? cnt[now] / _cnt[now] : cnt[now] / _cnt[now] + 1));
    }
    return (res == -1 ? INF : res);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m1 >> m2;
    if (m1 == 1)
        return cout << 0 << endl, 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    getPrimes(m1, m1);
    for (int i = 1; i <= n; i++)
    {
        getPrimeFac(i);
        ans = min(ans, solve());
    }
    cout << (ans == INF ? -1 : ans) << endl;
}