链接
点击跳转
题解
∑
a
i
<
Y
\sum a_i < Y
∑ai<Y也就意味着
∏
a
i
!
<
Y
\prod a_i! < Y
∏ai!<Y
所以答案至少是
0
0
0
那么我只需要对
X
X
X分解质因数，然后看一下每个质因数还能允许我容纳几个
x
x
x就可以了
分解质因数用Pollard Rho算法
代码
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1000010
#define maxe 1000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std
;
using namespace __gnu_pbds
;
typedef long long ll
;
typedef pair
<int,int> pii
;
typedef pair
<ll
,ll
> pll
;
ll
read(ll x
=0)
{
ll c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-0x30;
return f
*x
;
}
struct Pollard_Rho
{
ll
md(ll x
, ll p
){while(x
>p
)x
-=p
;return x
;}
ll
mult(ll a
, ll b
, ll p
)
{
ll ans
=0, t
=a
;
for(;b
;b
>>=1,t
=md(t
+t
,p
))if(b
&1)ans
=md(ans
+t
,p
);
return ans
;
}
ll
pow(ll a
, ll b
, ll p
)
{
ll ans
=1, t
=a
;
for(;b
;b
>>=1,t
=mult(t
,t
,p
))if(b
&1)ans
=mult(ans
,t
,p
);
return ans
;
}
bool MR(ll n
)
{
ll a
, t
, u
, i
, x
, y
, tim
=20;
if(n
==2)return true;
if(~n
&1)return false;
if(n
==3 or n
==5)return true;
if(n
%3==0 or n
%5==0)return false;
for(t
=0,u
=n
-1;~u
&1;u
>>=1,t
++);
while(tim
--)
{
a
=rand()%(n
-1)+1;
for(y
=x
=pow(a
,u
,n
),i
=1;i
<=t
;i
++)
{
x
=mult(x
,x
,n
);
if(x
==1 and y
!=n
-1 and y
!=1)return false;
y
=x
;
}
if(x
!=1)return false;
}
return true;
}
ll
pollard_rho(ll n
, ll c
)
{
ll i
, k
, x
=rand()%n
, y
=x
, d
;
for(i
=1,k
=2;;i
++)
{
x
=(mult(x
,x
,n
)+c
)%n
;
d
=__gcd(y
>x
?y
-x
:x
-y
,n
);
if(d
>1 and d
<n
)return d
;
if(x
==y
)return n
;
if(i
==k
)y
=x
,k
<<=1;
}
}
void find(ll n
, ll c
, map
<ll
,ll
>& ans
)
{
if(n
==1)return;
if(MR(n
)){ans
[n
]++;return;}
ll p
=pollard_rho(n
,c
);
for(;p
==n
;c
++)p
=pollard_rho(n
,c
);
find(p
,c
,ans
), find(n
/p
,c
,ans
);
}
map
<ll
,ll
> run(ll n
)
{
map
<ll
,ll
> ans
;
find(n
,1,ans
);
return ans
;
}
};
int main()
{
ll T
=read();
Pollard_Rho PR
;
while(T
--)
{
ll N
=read(), X
=read(), Y
=read(), i
;
vector
<ll
> a(N
+5);
rep(i
,1,N
)a
[i
]=read();
auto lis
= PR
.run(X
);
ll ans
=linf
;
for(auto pr
:lis
)
{
ll cnt
=0;
rep(i
,1,N
)
{
ll t
=a
[i
], p
=0;
while(t
)
{
p
+= t
/pr
.first
;
t
/=pr
.first
;
}
cnt
-= p
;
}
ll t
=Y
, p
=0;
while(t
)
{
p
+= t
/pr
.first
;
t
/=pr
.first
;
}
cnt
+= p
;
ans
= min(ans
,cnt
/pr
.second
);
}
printf("%lld\n",ans
);
}
return 0;
}
