思路转化

题目大意是这样的：给出数字\(N\)，\(m_1\)，\(m_2\)，\(S_{i[1\dots N]}\)，求最小的\(t\)，使得某一\(S_i^t \; mod\; m_1^{m_2}\)。

所以之后就非常的显然了，我们只要分析出每一个数的质因数与\(m_1\)的质因数的关系即可。如果有一个数\(c\)的质因数集为\(A\)，那么我们可以遍历\(m_1\)的质因数集，记录答案。如果质因数集不包含\(m_1\)的质因数集直接退出。

代码

// P1069.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int MX_N = 30020, INF = 0x3f3f3f3f;
ll n, m1, m2, arr[MX_N], pipePrime[MX_N], cellPrime[MX_N], lit, ans = INF;
int main()
{
    scanf("%lld%lld%lld", &n, &m1, &m2);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    if (m1 == 1)
    {
        printf("0");
        return 0;
    }
    for (int i = 2; m1 != 1; i++)
    {
        while (!(m1 % i))
            m1 /= i, pipePrime[i] += m2;
        lit = max(lit, (ll)i);
    }
    for (int i = 1; i <= n; i++)
    {
        ll now = 0;
        for (int j = 2; j <= lit; j++)
            if (pipePrime[j] != 0)
            {
                ll tim = 0;
                while (!(arr[i] % j))
                    arr[i] /= j, tim++;
                if (!tim)
                {
                    now = INF;
                    break;
                }
                now = max(now, (pipePrime[j] - 1) / tim);
            }
        ans = min(ans, now);
    }
    if (ans != INF)
        printf("%lld", ans + 1);
    else
        printf("-1");
    return 0;
}