题解：P17735 [ICPC 2019 Xuzhou R] Multiply

starowo · 2026-10-22 20:14:06 · 题解

题意

给定数组 a 和两个数 X,Y，设 Z=\prod a_i!，求最大的 i 使 Z\cdot X^i\mid Y!。

分析

我们设 f(x,p) 代表对 x 进行质因数分解后，质数 p 的指数。

那么有 f(Z,p)=\sum f(a_i!,p)。又由于素数 p 在 Y! 中指数为 f(Y!,p)，所以 X 的指数 i 要满足 i\cdot f(X,p)\le f(Y!,p)-\sum_{k=1}^{n} f(a_k!,p)。

故对于每个 p\mid X，i\le \left \lfloor \dfrac{f(Y!,p)-\sum_{k=1}^{n} f(a_k!,p)}{f(X,p)}\right \rfloor。

问题转化完毕，考虑如何解决。

我们知道，对于计算 f(x!,p)，有勒让德（Legendre）公式：

其中 p^k>x 时式子下取整为 0，故求和仅限有限项。

根据该公式求解 f(Z,p) 与 f(Y!,p)，用 Miller-Rabin 与 Pollard-Rho 分解 X 即可。

别忘了开 __int128。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5,inf=1e18;
mt19937 rnd(time(0));
inline void read(__int128 &x){
    x=0;
    int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    x*=f;
}
__int128 abs(__int128 x){
    return (x>0?x:-x);
}
__int128 gcd(__int128 a,__int128 b){
  if(b==0) return a;
  return gcd(b,a%b);
}
__int128 qmul(__int128 x,__int128 n,__int128 p){
    __int128 res=0;
    while(n){
        if(n&1) res=(res+x)%p;
        x=(x+x)%p;
        n>>=1;
    }
    return res;
}
__int128 qpow(__int128 x,__int128 n,__int128 p){
    __int128 res=1;
    while(n){
        if(n&1) res=res*x%p;
        x=x*x%p;
        n>>=1;
    }
    return res;
}
bool mr(__int128 n){
    if(n==2) return true;
    if(n<=1||n%2==0) return false;
    vector<__int128> base={2,325,9375,28178,450775,9780504,1795265022};
    __int128 s=0,u=n-1;
    while(u%2==0){
        u/=2;
        s++;
    }
    for(auto a:base){
        if (a%n==0) continue;
        __int128 x=qpow(a,u,n);
        if(x==1||x==n-1) continue;
        bool flag=false;
        for(int r=1;r<s;r++){
            x=x*x%n;
            if(x==n-1){
                flag=true;
                break;
            }
        }
        if(!flag) return false;
    }
    return true;
}
__int128 pr(__int128 x){
    __int128 s=0,t=0;
    __int128 c=(__int128)rnd()%(x-1)+1;
    int step=0,goal=1;
    __int128 val=1;
    for(goal =1;;goal<<=1,s=t,val=1){  
        for (step=1;step<=goal;++step){
            t=(qmul(t,t,x)+c)%x;
            val=qmul(val,abs(t-s),x);
            if((step % 127)==0){
                __int128 d=gcd(val,x);
                if (d>1) return d;
            }
        }
        __int128 d=gcd(val,x);
        if(d>1) return d;
    }
}
__int128 query(__int128 x){
    if(x<2) return 1;
    if(mr(x)) return x;
    __int128 y=x;
    while(y>=x) y=pr(y);
    return max(query(y),query(x/y));
}
int calcc(int x,int y){
    int res=0,xx=1;
    for(int i=1;i<=64;i++){
        xx*=x;
        if(xx<0||y/xx==0) break;
        res+=y/xx;
    }
    return res;
}
int n,x,y,a[N],ans;
vector<int> prime;
int calc(int xx){
    int res=calcc(xx,y);
    for(int i=1;i<=n;i++) res-=calcc(xx,a[i]);
    int cnt=0,tmp=x;
    while(tmp%xx==0) cnt++,tmp/=xx;
    return res/cnt;
}
void solve(){
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++) cin>>a[i];
    prime.clear();
    int xx=x;
    while(xx>1){
        __int128 yy=query(xx);
        while(xx%yy==0) xx/=yy;
        prime.push_back(yy); 
    }
    ans=inf;
    for(auto i:prime) ans=min(ans,calc(i));
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}