题解：P17735 [ICPC 2019 Xuzhou R] Multiply

· · 题解

题意

给定 n 个正整数 a_1, \dots, a_n 和两个整数 x, y 。令：

Q = \frac{y!}{a_1! \times a_2! \times \cdots \times a_n!}

求最大的非负整数 k ，使得 x ^ k 能整除 Q 。

思路

感觉出思路不是很难。

设 f(n, p_j) = \sum_{t \ge 1}\left\lfloor \frac{n}{p_j ^ t} \right\rfloor 表示 n! 中质数 p_j 的指数，c_j 表示 x 中质数 p_j 的指数。

因此， \dfrac{y!}{\prod_{i = 1} ^ {n}a_i!} 中质数 p_j 的指数为： s_j = f(y, p_j) - \sum_{i = 1}^{n} f(a_i, p_j) 。每乘一次 x ，会消耗 c_j 个 p_j ，所以答案为： \min_{1 \le j \le m}\left\lfloor \frac{s_j}{c_j} \right\rfloor 。

实现上，我们考虑使用 Pollard-Rho 分解出 x 的所有质因数，其它细节看代码即可。

:::success[Code]

// I often find myself reminiscing about the past.
// Moments of life freeze in my mind.
// I cut, fold, and curl the time behind me, kneading it into the white clouds drifting across the sky.
// Even clouds have their distinctions: cumulus clouds are heavy, while cirrus clouds are ethereal.
// The moments in life that strike me with awe pass through my thoughts and remain unforgettable forever, while the more ordinary, everyday memories leave behind only fragments under the erosion of time.
// Reminiscence is like entering a dream—too clear, and it cannot delight my imagination; too vague, and it sinks into nothingness.
// Only the mist-shrouded mountains and rivers, the veiled woman—that perfect haziness—can satisfy my longing for beauty.
// Reminiscence always wraps me, unbidden, in the yellowed pages of the past.
// Friends parted and reunited, streets demolished and rebuilt—each clue helps me set out from a specific moment and sail upstream against the river of time.
// The days gone by cannot be relived; I am merely a passerby.
// Yet I still long to leave myself moments of leisure on every journey into memory—to pause before a scene, to gaze across the haze of years at my former self, and to savor as much sweetness as I can.
// If beautiful times once flowed through my body, I am already content.
// The past has solidified.
// I carry my memories forward, but I often neglect to tend to them, and so the memories themselves keep changing their forms.
// This brings a certain challenge to my journeys of recollection.
// Where should I linger? I ask myself.

#include <bits/stdc++.h>
// #define LOCAL

namespace ly {
    // 苦情巨树啊
    // 你听见了吗
    // 如果我也已经爱上了他
    // 我愿意用我们相识的一点一滴以及我的全部妖力来起誓
    // 让我们来生相见吧
    namespace IO {
        #ifndef LOCAL
            constexpr auto maxn = 1 << 21;
            char in[maxn], out[maxn], *p1 = in, *p2 = in, *p3 = out;
            #define getchar() (p1 == p2 && (p2 = (p1 = in) + fread(in, 1, maxn, stdin), p1 == p2) ? EOF : *p1++)
            #define flush() (fwrite(out, 1, p3 - out, stdout))
            #define putchar(x) (p3 == out + maxn && (flush(), p3 = out), *p3++ = (x))
            class Flush{ public: ~Flush(){ flush(); } } _;
        #endif
        namespace usr {
            template <typename type>
            inline type read(type &x){
                x = 0; bool flag(0); char ch = getchar();
                while(!isdigit(ch)) flag ^= ch == '-', ch = getchar();
                while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
                return flag ? x = -x : x;
            }
            template <typename type>
            inline void write(type x){
                x < 0 ? x = -x, putchar('-') : 0;
                static short Stack[50], top(0);
                do Stack[++top] = x % 10, x /= 10; while(x);
                while(top) putchar(Stack[top--] | 48);
            }
            inline char read(char &x){
                do x = getchar(); while(isspace(x));
                return x;
            }
            inline char write(const char &x){
                return putchar(x);
            }
            inline void read(char *x){
                static char ch;
                read(ch);
                do *(x++) = ch; while(!isspace(ch = getchar()) && ~ch);
            }
            template <typename type> inline void write(type *x){
                while(*x) putchar(*(x++));
            }
            inline void read(std::string &x){
                static char ch; read(ch), x.clear();
                do x += ch; while(!isspace(ch = getchar()) && ~ch);
            }
            inline void write(const std::string &x){
                for(int i = 0, len = x.length(); i < len; ++i) putchar(x[i]);
            }
            template <typename type, typename...T> inline void read(type &x, T&...y){
                read(x), read(y...);
            }
            template <typename type, typename...T>
            inline void write(const type &x, const T&...y){
                write(x), putchar(' '), write(y...), sizeof...(y) ^ 1 ? 0 : putchar('\n');
            }
            template <typename type>
            inline void put(const type &x, bool flag = 0){
                write(x), flag ? putchar('\n') : putchar(' ');
            }
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    } using namespace IO::usr;
} using namespace ly::IO::usr;

#define FILE
#define IOS() std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0)
#define mp std::make_pair
#define re register
using ll = long long;
using ull = unsigned long long;
using ld = double;
// #define int long long
using pii = std::pair <int, int>;

std::mt19937_64 rnd(time(0));
ll gcd(ll a, ll b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}
inline ll mul(ll a, ll b, ll mod){
    ull c = (ull)a * (ull)b - (ull)((long ld)a / mod * b + 0.5L) * (ull)mod;
    if(c < (ull)mod) return c;
    return c + mod;
}
inline ll qpow(ll a, ll b, ll mod){
    ll ans = 1;
    while(b){
        if(b & 1) ans = mul(ans, a, mod);
        a = mul(a, a, mod), b >>= 1;
    }
    return ans;
}
inline bool MR(ll p){
    if(p < 2) return 0;
    if(p == 2 || p == 3) return 1;
    ll d = p - 1, r = 0;
    while(!(d & 1)) d >>= 1, ++r;
    for(ll k = 0; k < 10; ++k){
        ll a = rnd() % (p - 2) + 2, x = qpow(a, d, p);
        if(x == 1 || x == p - 1) continue;
        for(int i = 0; i < r - 1; ++i){
            x = mul(x, x, p);
            if(x == p - 1) break;
        }
        if(x != p - 1) return 0;
    }
    return 1;
}
inline ll PR(ll x){
    ll s = 0, t = 0, c = rnd() % (x - 1) + 1, val = 1;
    for(int i = 1; ; i <<= 1, s = t, val = 1){
        for(int j = 1; j <= i; ++j){
            t = (mul(t, t, x) + c) % x, val = mul(val, std::llabs(t - s), x);
            if(j % 127 == 0){
                ll g = gcd(val, x);
                if(g > 1) return g;
            }
        }
        ll g = gcd(val, x);
        if(g > 1) return g;
    }
}
ll ans;
void fac(ll x){
    if(x <= ans || x < 2) return ;
    if(MR(x)){
        ans = std::max(ans, x);
        return ;
    }
    ll p = x;
    while(p >= x) p = PR(x);
    while(x % p == 0) x /= p;
    fac(x), fac(p);
}

inline ll calc(ll x, ll y){
    ll cnt = 0;
    while(y) y /= x, cnt += y;
    return cnt;
}
constexpr int N = 1e6 + 5;
ll a[N], x, y, n, pre;
inline ll check(ll z){
    ll cnt = calc(z, y);
    for(int i = 1; i <= n; ++i) cnt -= calc(z, a[i]);
    ll k = 0, p = pre;
    while(p % z == 0) p /= z, ++k;
    return cnt / k;
}
inline void solve(){
    read(n, x, y), pre = x;
    for(int i = 1; i <= n; ++i) read(a[i]);
    ll k = 4e18;
    while(x > 1){
        ans = 0;
        fac(x);
        while(x % ans == 0) x /= ans;
        k = std::min(k, check(ans));
    }
    put(k, 1);
}
int main(){
    #ifndef FILE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    int t;
    read(t);
    while(t--) solve();
    return 0;
}

// 阿乌拉,投降吧
// ......
// 阿乌拉,站在你面前的是活了上千年的魔法使

:::