A6细胞分裂(用心求点赞)

$题目大意是找到一个s^k使得s^k\equiv0(\bmod m1^{m2})即s^k\%m1^{m2}==0且k最小$
$给你n个s让你求所有s对应k的最小值$

$一.M的处理$

$因为我们m2和m1过大所以无法直接处理出m1^{m2}的值$
$考虑素因(质)数分解$
$令M=m1=p_1^{a_1}*{p_2}^{a_2}*{p_3}^{a_3}\cdots(p_1,p_2,\cdots均为素(质)数,a_1,a_2,\cdots均为整数)即该式为m1的素(质)因数分解$
$则M=m1^{m2}=(p_1^{a_1}*{p_2}^{a_2}*{p_3}^{a_3}\cdots)^{m2}=p_1^{a_1m2}*{p_2}^{a_2m2}*{p_3}^{a_3m2}\cdots$
$那么我们可以维护每个p_i和a_i可以开个struct维护$

$二.s的处理$

$那面对2*10^9的s我们肯定不能用素(质)因数分解$
$因为我们要让s^k\%m1^{m2}==0就是说s^k是m1^{m2}的倍数所以s^k必然至少有因数a_1个p_1,a_2个p_2\cdots$
$因此对于每个s我们将它依次除以前文得到的p_1,p_2,p_3\cdots$
$其中如果s没有一种M含的素因数,这种情况就不成立$
$否则必然可以凑出因数a_1个p_1,a_2个p_2\cdots$
$在成立情况下令s=n*p_1^{b_1}*p_2^{b_2}\cdots(b_1,b_2,\cdots均为整数)$

$三.求解$

$所以s^k=n^k*p_1^{kb_1}*p_2^{kb_2}\cdots(b_1,b_2,\cdots均为整数)$
$且s^k是m1^{m2}的倍数则kb_i\geq a_i$
$在已知a_i,b_i的情况下,便可以求出k的范围$
$最后根据解集求出k在对于所有k取最小值可得答案$

$四.根据思路完成代码(小练习,代码在下面)$

#include<algorithm>
#include<iostream>
#include<map>
#include<vector>
using namespace std;
struct node{
    int n;
    long long cnt;
};
long long m1,m2,n,s,ans;
vector<node>v;
long long solve(long long x){
    long long cnt,res=0;
    for (int i=0;i<v.size();i++){
        long long a=v[i].n,b=v[i].cnt;
        cnt=0;
        if (①){
            return -1;
        }
        while (x%a==0){
            cnt++;
            x/=a;
        }
        res=max(res,②);
    }
    return res;
}
int main(){
    cin>>n>>m1>>m2;
    for (int i=2;i<=m1;i++){
        if (m1%i==0){
            v.push_back(③);
        }
        while (m1%i==0){
            v[v.size()-1].cnt+=④;
            m1/=i;
        }
    }
    ans=-1;
    for (int i=1;i<=n;i++){
        cin>>s;
        long long res=solve(s);
        if (res!=-1){
            if (ans==⑤)ans=res;
            else ans=min(ans,res);
        }
    }
    cout<<ans;
    return 0;
}

①
$A.x\%a==0$
$B.x\%a!=0$
$C.x/a!=0$
$D.x/a==0$
②
$A.b/cnt+(b\%cnt==0)$
$B.b/cnt$
$C.b/cnt+(b\%cnt!=0)$
$D.b\%cnt$
③
$A.\{i,0\}$
$B.\{i,m2\}$
$C.\{i,m1\}$
$D.\{m2,i\}$
④
$A.1$
$B.i$
$C.m1$
$D.m2$
⑤
$A.0$
$B.-1$
$C.m1$
$D.m2$

$五.正解$

#include<algorithm>
#include<iostream>
#include<map>
#include<vector>
using namespace std;
struct node{
    int n;
    long long cnt;
};
long long m1,m2,n,s,ans;
vector<node>v;
long long solve(long long x){
    long long cnt,res=0;
    for (int i=0;i<v.size();i++){
        long long a=v[i].n,b=v[i].cnt;
        cnt=0;
        if (x%a!=0){
            return -1;
        }
        while (x%a==0){
            cnt++;
            x/=a;
        }
        res=max(res,b/cnt+(b%cnt!=0));
    }
    return res;
}
int main(){
    cin>>n>>m1>>m2;
    for (int i=2;i<=m1;i++){
        if (m1%i==0){
            v.push_back({i,0});
        }
        while (m1%i==0){
            v[v.size()-1].cnt+=m2;
            m1/=i;
        }
    }
    ans=-1;
    for (int i=1;i<=n;i++){
        cin>>s;
        long long res=solve(s);
        if (res!=-1){
            if (ans==-1)ans=res;
            else ans=min(ans,res);
        }
    }
    cout<<ans;
    return 0;
}

$参考答案:BCADB$
$创作不易,求点赞$