无脑写法(直接输出无解的情况)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<-1;
    return 0;
}

小数据写法(30~50分)

【解题思路】 从小到大枚举时间，针对每个s，找到最小的满足s%$m_1^{m_2}==0$的时间，时间可以估计一个比较小的值。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    LL n,m1,m2;
    cin>>n>>m1>>m2;
    LL m=1;
    for(int i=1;i<=m2;i++)
    {
        m=m*m1;
    }
    LL ans=1000000000;
    for(int i=1;i<=n;i++)
    {
        LL s=1,s1;
        cin>>s1;
        LL j;
        for(j=0;j<=60;j++)
        {
          
            if(s%m==0)
            {
                ans=min(ans,j);
                break;
            } 
            s*=s1;
        }
    }
    if(ans!=1000000000)
    {
        cout<<ans;
    }
    else
    {
        cout<<-1;
    }
    return 0;
}

正解

【算法分析】 题目要找到最小的t,使得$s^t$%$m_1^{m_2}==0$,我们假设$m_1$分解质因数的结果是$p_1 \times p_2...p_n$等价于$s^t$在分解了质因数以后会大于等于$m_1^{m_2}$中的每个质因子。

#include<bits/stdc++.h>
using namespace std;
const int INF=1e8;
map<int,int> get(int x) //分解质因数
{
	map<int,int> res;
	for(int i=2;i<=x/i;i++)
	{
		while(x%i==0)
		{
			x/=i;
			res[i]++;
		}
	}
	if(x>1) res[x]=1;
	return res;
}
int main()
{
	int n,m1,m2;
	cin>>n>>m1>>m2;
	auto a=get(m1);
	int res=INF;
	while(n--)
	{
		int s;
		cin>>s;
		auto b=get(s); //得到s分解质因数的结果
		int t=0;
		for(auto x:a) //枚举m1里面的每个因子
		{
			int k=x.first,v=x.second;
			if(!b.count(k)) //s里面没有包含m1的某个因子
			{
				t=INF;
				break;
			}
			else
			{
				t=max(t,(v*m2+b[k]-1)/b[k]); //计算得到m1的因子的倍数的最小时间
				//   b[k]*t>=v*m2    t是时间上取整的结果
			}
		}
		res=min(res,t); //t表示的s的是m1^m2的倍数的最小时间,res是所有的s里面的最小时间
	}
	if(res==INF) //没有更新过 
	{
	    res=-1;
	}
	cout<<res;
	return 0;
}