题解：P17735 [ICPC 2019 Xuzhou R] Multiply

· · 题解

碎碎念

思维难度严格小于代码模板。

sol

实际上就是说 Y! 除掉 \prod a_i! 后有多少个 X。

比如说 10! 里有两个 10。

这个就很简单的数论啊，比如我们设 \dfrac{Y!}{\prod a_i!}=W（当然不是真的在代码里要除，下面为了方便处理他们除的结果的质因数）。

我们先把 X 质因数分解掉，拆成 \prod p_{i}^{b_{i}} 的形式。

然后统计 W 里 p_i 的个数 c_i，X 的个数就是 \min \Big\lfloor\dfrac{c_i}{b_i}\Big\rfloor。

解释一下为什么是 \min，原因是木桶效应，比如 X=24=2^3\times 3，然后 W 里有 8 个 2，3 个 3，那你就只能凑出 \Big\lfloor\dfrac{8}{3}\Big\rfloor = 2 个 X 而不能凑出 \Big\lfloor\dfrac{3}{1}\Big\rfloor = 3 个，原因是你的 2 不够，成为了短板。

然后在代码里不需要真的求出 W，p_i 对应的 c_i 直接就是 calc(Y,p_i)-\sum calc(a_i,p_i)，其中 calc(p,q) 是统计 p! 里有几个 q（勒让德定理），时间 O(n\log X\log Y)。

发现困难的是做 X 的质因数分解，O(\sqrt V) 是过不去的，我们只能去写 Pollard's Rho 了，时间 O(\sqrt[4]{V})。

最后的时间复杂度是 O(T(\sqrt[4]{V}+n\log X \log Y))。

然后就是不要学煮波赛时求的 \min\dfrac{calc(Y,p_i)}{b_i} - \min \dfrac{\sum calc(a_i,p_i)}{b_i}，正确的是 \min \dfrac{calc(Y,p_i)-\sum calc(a_i,p_i)}{b_i}，因为犯这个唐吃了两发罚时。

code

const int N = 1e5 + 2 ;
int T,n ;
ll x,y,a[N] ;
int tot,b[105] ;
ll p[105] ;
mt19937_64 rng(67676767) ;
vector<ll> tmp ;
inline ll qpow (ll a,ll b,fl mod) {
    ll res = 1 ; a %= mod ;
    while (b) {
        if (b & 1) res = (lll)res * a % mod ;
        a = (lll)a * a % mod ;
        b >>= 1 ;
    }
    return res ;
}
inline bool mr (fl n) {
    if (n < 2) return false ;
    if (n == 2 || n == 3 || n == 5 || n == 7) return true ;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false ;
    static const ll bases[] = {2,3,5,7,11,13,17,19,23,29,31,37} ;
    ll d = n - 1,s = 0 ;
    while (!(d & 1)) d >>= 1,++s ;
    for (re int i = 0 ; i < 12 ; ++i) {
        ll a = bases[i] ;
        if (n <= a) break ;
        ll x = qpow(a,d,n) ;
        if (x == 1 || x == n - 1) continue ;
        bool ok = false ;
        for (re int r = 1 ; r < s ; ++r) {
            x = (lll)x * x % n ;
            if (x == n - 1) {ok = true ; break ;}
        }
        if (!ok) return false ;
    }
    return true ;
}
inline ll rho (fl n) {
    ll s = 0,t = 0,c = rng() % (n - 1) + 1,val = 1 ;
    for (re int goal = 1 ; ; goal <<= 1,s = t,val = 1) {
        for (re int step = 1 ; step <= goal ; ++step) {
            t = ((lll)t * t + c) % n ;
            val = (lll)val * (s > t ? s - t : t - s) % n ;
            if (step % 127 == 0) {
                ll d = __gcd(val,n) ;
                if (d > 1) return d ;
            }
        }
        ll d = __gcd(val,n) ;
        if (d > 1) return d ;
    }
}
inline void dfs (fl n) {
    if (n <= 1) return ;
    if (mr(n)) {tmp.push_back(n) ; return ;}
    ll d = n ;
    while (d >= n) d = rho(n) ;
    dfs(d) ;
    dfs(n / d) ;
}
inline void init (fl n) {
    tot = 0 ;
    tmp.clear() ;
    dfs(n) ;
    sort(tmp.begin(),tmp.end()) ;
    for (re int i = 0 ; i < tmp.size() ; ++i) {
        if (!tot || p[tot] != tmp[i]) p[++tot] = tmp[i],b[tot] = 1 ;
        else ++b[tot] ;
    }
}
inline ll fun (ll v,ll t) {
    ll res = 0 ;
    while (v) v /= t,res += v ;
    return res ;
}
inline ll calc () {
    ll tmp,res = LLONG_MAX ;
    for (re int i = 1 ; i <= tot ; ++i) {
        tmp = fun(y,p[i]) ;
        for (re int j = 1 ; j <= n ; ++j) tmp -= fun(a[j],p[i]) ;
        res = min(res,tmp / b[i]) ;
    }
    return res ;
}
inline void solve () {
    read(n,x,y) ;
    init(x) ;
    for (re int i = 1 ; i <= n ; ++i) read(a[i]) ;
    return write(calc(),endl) ;
}
int main () {
    read(T) ;
    while (T--) solve() ;
    return 0 ;
}