定义

任何一个大于 1 的数都可以被分解成有限个质数乘积的形式

其中$p1<p2<...<pm$，为素数，$C_i$为正整数

显然 n 最多仅有一个大于 $\sqrt{n}$的质因子（若有两个的话，他们的乘积就大于 n 了）

试除法

枚举因子，将当前因子全部除尽即可，时间复杂度$O(\sqrt{n})$

int cnt;//质因子数量
int num[MAX], p[MAX];//素数个数，素数
void divide(int n){
    cnt = 0;
    if(n == 1){p[++cnt] = 1;num[cnt] = 1;return;}//1特判
    for(int i = 2; i * i <= n; ++i){
        if(n % i == 0){
            p[++cnt] = i;num[cnt] = 0;
            while (n % i == 0) {n /= i;++num[cnt];}
        }
    }
    if(n > 1){p[++cnt] = n;num[cnt] = 1;}//特判n是素数
//    rep(i, 1, cnt){
//      cout<<p[i]<<'^'<<num[i]<<endl;
// }
}

Pollard Rho 算法

  对于数据较大的情况，如 $n<=1e18$，有用来分解其因数的Pollard Rho 算法。

模版：

const int N = 1e5 + 7;
ll x, y, a[N];
ll max_factor;
struct BigIntegerFactor {
    const static int N = 1e6 + 7;
    ll prime[N], p[N], fac[N], sz, cnt;//多组输入注意初始化cnt = 0
    inline ll mul(ll a, ll b, ll mod) {//WA了尝试改为__int128或慢速乘
        if (mod <= 1000000000)
            return a * b % mod;
        return (a * b - (ll)((long double)a / mod * b + 1e-8) * mod + mod) % mod;
    }
    void init(int maxn) {
        int tot = 0;
        sz = maxn - 1;
        for (int i = 1; i <= sz; ++i)
            p[i] = i;
        for (int i = 2; i <= sz; ++i) {
            if (p[i] == i)
                prime[tot++] = i;
            for (int j = 0; j < tot && 1ll * i * prime[j] <= sz; ++j) {
                p[i * prime[j]] = prime[j];
                if (i % prime[j] == 0)
                    break;
            }
        }
    }
    ll qpow(ll a, ll x, ll mod) {
        ll res = 1ll;
        while (x) {
            if (x & 1)
                res = mul(res, a, mod);
            a = mul(a, a, mod);
            x >>= 1;
        }
        return res;
    }
    bool check(ll a, ll n) {//二次探测原理检验n
        ll t = 0, u = n - 1;
        while (!(u & 1)){t++; u >>= 1;}
        ll x = qpow(a, u, n), xx = 0;
        while (t--) {
            xx = mul(x, x, n);
            if (xx == 1 && x != 1 && x != n - 1)
                return false;
            x = xx;
        }
        return xx == 1;
    }
    bool miller(ll n, int k) {
        if (n == 2)
            return true;
        if (n < 2 || !(n & 1))
            return false;
        if (n <= sz)
            return p[n] == n;
        for (int i = 0; i <= k; ++i) {//测试k次
            if (!check(rand() % (n - 1) + 1, n))
                return false;
        }
        return true;
    }
    inline ll gcd(ll a, ll b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    inline ll Abs(ll x) {
        return x < 0 ? -x : x;
    }
    ll Pollard_rho(ll n) {//基于路径倍增的Pollard_Rho算法
        ll s = 0, t = 0, c = rand() % (n - 1) + 1, v = 1, ed = 1;
        while (1) {
            for (int i = 1; i <= ed; ++i) {
                t = (mul(t, t, n) + c) % n;
                v = mul(v, Abs(t - s), n);
                if (i % 127 == 0) {
                    ll d = gcd(v, n);
                    if (d > 1)
                        return d;
                }
            }
            ll d = gcd(v, n);

            if (d > 1)
                return d;
            s = t;
            v = 1;
            ed <<= 1;
        }
    }
    void getfactor(ll n) {//得到所有的质因子(可能有重复的)
        if (n <= sz) {
            while (n != 1){fac[++cnt] = p[n]; n /= p[n];}
            max_factor = max_factor > p[n] ? max_factor : p[n];
            return;
        }
        if (miller(n, 6)) {
            fac[++cnt] = n;
            max_factor = max_factor > n ? max_factor : n;
        }
        else {
            ll d = n;
            while (d >= n)
                d = Pollard_rho(n);
            getfactor(d);
            getfactor(n / d);
        }
        return ;
    }
    void getp(ll n){//得到所有的素因子及其个数
        map<ll, ll>mp;//存素数及个数
        cnt = 0;
        getfactor(n);
        for(int i = 1; i <= cnt; ++i){
            ++mp[fac[i]];
        }
        map<ll, ll>::iterator it;
        for(it = mp.begin(); it != mp.end(); ++it){
            cout<<it->first<<' '<<it->second<<endl;
        }
    }
} Q;
void work(){
    //Q.init(N - 1);//如果代码超时且仅需要分解大数的质因数可以用这句话，否则不要用
    ll n;cin>>n;
    Q.cnt = 0;
    max_factor = -1;
    Q.getfactor(n);
    //if(Q.cnt == 1)cout<<"Prime\n";
    //else cout<<max_factor<<endl;
		//Q.getp(n);
}

【模板】Pollard-Rho算法（Luogu P4718）

题目描述：

T组数据，每组数据输入一个数 n ，检验 n 是否是质数，是质数就输出 Prime。如果不是质数，输出它的最大质因子。

思路：

模版题，大数质因数分解后比较每个质因数，找到最大的就行

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mod 998244353
#define y1 y114514
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

typedef long long ll;
const int N = 1e5 + 7;
ll x, y, a[N];
ll max_factor;
struct BigIntegerFactor {
    const static int N = 1e6 + 7;
    ll prime[N], p[N], fac[N], sz, cnt; //多组输入注意初始化cnt = 0
    inline ll mul(ll a, ll b, ll mod) {          //WA了尝试改为__int128或慢速乘
        if (mod <= 1000000000)
            return a * b % mod;
        return (a * b - (ll)((long double)a / mod * b + 1e-8) * mod + mod) % mod;
    }
    void init(int maxn) {
        int tot = 0;
        sz = maxn - 1;
        for (int i = 1; i <= sz; ++i)
            p[i] = i;
        for (int i = 2; i <= sz; ++i) {
            if (p[i] == i)
                prime[tot++] = i;
            for (int j = 0; j < tot && 1ll * i * prime[j] <= sz; ++j) {
                p[i * prime[j]] = prime[j];
                if (i % prime[j] == 0)
                    break;
            }
        }
    }
    ll qpow(ll a, ll x, ll mod) {
        ll res = 1ll;
        while (x) {
            if (x & 1)
                res = mul(res, a, mod);
            a = mul(a, a, mod);
            x >>= 1;
        }
        return res;
    }
    bool check(ll a, ll n) {                     //二次探测原理检验n
        ll t = 0, u = n - 1;
        while (!(u & 1)){t++; u >>= 1;}
        ll x = qpow(a, u, n), xx = 0;
        while (t--) {
            xx = mul(x, x, n);
            if (xx == 1 && x != 1 && x != n - 1)
                return false;
            x = xx;
        }
        return xx == 1;
    }
    bool miller(ll n, int k) {
        if (n == 2)
            return true;
        if (n < 2 || !(n & 1))
            return false;
        if (n <= sz)
            return p[n] == n;
        for (int i = 0; i <= k; ++i) {            //测试k次
            if (!check(rand() % (n - 1) + 1, n))
                return false;
        }
        return true;
    }
    inline ll gcd(ll a, ll b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    inline ll Abs(ll x) {
        return x < 0 ? -x : x;
    }
    ll Pollard_rho(ll n) {                 //基于路径倍增的Pollard_Rho算法
        ll s = 0, t = 0, c = rand() % (n - 1) + 1, v = 1, ed = 1;
        while (1) {
            for (int i = 1; i <= ed; ++i) {
                t = (mul(t, t, n) + c) % n;
                v = mul(v, Abs(t - s), n);
                if (i % 127 == 0) {
                    ll d = gcd(v, n);
                    if (d > 1)
                        return d;
                }
            }
            ll d = gcd(v, n);

            if (d > 1)
                return d;
            s = t;
            v = 1;
            ed <<= 1;
        }
    }
    void getfactor(ll n) {                         //得到所有的质因子(可能有重复的)
        if (n <= sz) {
            while (n != 1){fac[++cnt] = p[n]; n /= p[n];}
            max_factor = max_factor > p[n] ? max_factor : p[n];
            return;
        }
        if (miller(n, 6)) {
            fac[++cnt] = n;
            max_factor = max_factor > n ? max_factor : n;
        }
        else {
            ll d = n;
            while (d >= n)
                d = Pollard_rho(n);
            getfactor(d);
            getfactor(n / d);
        }
        return ;
    }
    void getp(ll n){
        map<ll, ll>mp;
        cnt = 0;
        getfactor(n);
        for(int i = 1; i <= cnt; ++i){
            ++mp[fac[i]];
        }
        map<ll, ll>::iterator it;
        for(it = mp.begin(); it != mp.end(); ++it){
            cout<<it->first<<' '<<it->second<<endl;
        }
    }
} Q;

void work(){
    //Q.init(N - 1);//如果代码超时且仅需要分解大数的质因数可以用这句话，否则不要用
    ll n;cin>>n;
    Q.cnt = 0;
    max_factor = -1;
    Q.getfactor(n);
    if(Q.cnt == 1)cout<<"Prime\n";
    else cout<<max_factor<<endl;
//    Q.getp(n);
}

int main() {
    int _t;cin>>_t;
    while (_t--) {
        work();
    }
    return 0;
}

分解问题的扩展

Problem A 阶乘分解（AcWing 197）

题目描述：

给定整数 N，试把阶乘 N!分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可

思路：

$n！ = p_{1}^{C_1} * p_{2}^{C_2} * p_{3}^{C_3} * ...*p_{m}^{C_m}$

我们需要求$C_1,C_2....$

一个显然的结论是：1到n中是p的倍数的数字有$\lfloor{\frac{n}{p}}\rfloor$个

所以对于一个质因子p来说:$n!$中含p的个数是$\lfloor{\frac{n}{p}}\rfloor + \lfloor{\frac{n^2}{p}}\rfloor + \lfloor{\frac{n^3}{p}}\rfloor....$

拿2来说就是n/2向下取整，这计算的是1到n中能贡献一个2的数量，再计算n/4向下取整，这计算的是1到n中能贡献两个2的数量，依次这样算下去就可以

所以这个题的思路是，先筛出所有的素数，然后挨个计算每个素数的C，然后输出就行

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
#define y1 y114514
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
ll a, b, c;
string s, t;

int tot;
int prime[100000];
bool vis[1000005];

void init(int n){
    for(int i = 2; i <= n; ++i){
        if(!vis[i])prime[++tot] = i;
        for(int j = 1; j <= tot && prime[j] * i <= n; ++j){
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0)break;
        }
    }
}

void work(){
    init(1000000);
    cin>>n;
    for(int i = 1; i <= tot && prime[i] <= n; ++i){
        ll ans = 0;
        ll x = n;
        while (x) {
            ans += x / prime[i];
            x /= prime[i];
        }
        cout<<prime[i]<<' '<<ans<<endl;
    }
}


int main(){
    io;
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

Problem C Divisors of the Divisors of an Integer（2018-2019 ACM-ICPC, Asia Dhaka Regional ContestC）

题目描述：

给出 n，问 n ! 的因子的因子的个数和

思路：

$n！ = p_{1}^{C_1} * p_{2}^{C_2} * p_{3}^{C_3} * ...*p_{m}^{C_m}$

单独分析其中一个p，有C个p，那有$1,p,p^2,p^3...,p^i,...,p^c$共1 + C个因子，每个因子$p^i$都有i+1个因子，合起来就是$1,2,3...c+1$,利用等差数列求和公式即可求出

求n!的p因子的个数还是要用到上个题的方法

最后将每个p的结果相乘就是答案

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 10000007
#define y1 y114514
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

//不改范围见祖宗!!!
#define MAX 300000 + 50
ll n, m, k, op;
int x, y, z;
ll a, b, c;
string s, t;

int tot;
int prime[100005];
bool vis[1000005];
void init(int n){
    for(int i = 2; i <= n; ++i){
        if(!vis[i])prime[++tot] = i;
        for(int j = 1; j <= tot && prime[j] * i <= n; ++j){
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0)break;
        }
    }
}

ll cal(ll x, ll p){
    ll ans = 0;
    while (x) {
        ans += x / p;
        x /= p;
    }
    return ans;
}

void work(){
    init(1000000);
    while (cin>>n && n) {
        ll ans = 1;
        for(int i = 1; i <= tot && prime[i] <= n; ++i){
            ll num = cal(n, prime[i]);
            ans *= (num + 1) * (num + 2) / 2;
            ans %= mod;
        }
        cout<<ans<<endl;
    }
}


int main(){
    io;
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

Problem D Multiply（2019 ACM- ICPC Asia Xuzhou Regional Contest E）

题目描述：

给 n 个数的序列a，定义 $Z = \prod_{i=1}^{n}{(a_i!)}$,给出X，Y，若$bi = Z * X^i$,求最大的 i 使得$b_i |Y!$

思路：

由于规定$\sum{a_i}<Y$，所以$Z|Y!$

故$b_i|Y! => (Z*X^i)|Y! =>X^i |\frac{Y!}{Z}$

对与$a|b$的条件是：对a质因数分解后变成$p_1^{c_1}*p_2^{c_2}*p_3^{c_3}...$,对b质因数分解后$p_1^{d_1}p_2^{d_2}p_3^{d_3}...$,a的所有质因子p_i必须在b中存在，且必须满足$d_i>=c_i$

对于X的一个质因子p，X质因子分解后有a个p，Y!有b个p，Z有c个p，则$i * a <=b-c$,$i=\lfloor{\frac{b-c}{a}}\rfloor$,贪心求出最小的 i 就是答案

所以我们先对X进行质因数分解，得到所有的质因子及个数，再对于一个质数p，我们对a_i进行循环计算a_i!有几个p，求个合，这就是c，再计算Y!有几个p，这就是b，然后计算$i=\lfloor{\frac{b-c}{a}}\rfloor$即可，最后对所有的 i 求最小值

计算N!有几个p的方法在上面介绍过了，写个函数算就行

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mod 998244353
#define y1 y114514
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

const int N = 1e5 + 7;
ll x, y, tr[N];
ll max_factor;
struct BigIntegerFactor {
    const static int N = 1e6 + 7;
    ll prime[N], p[N], fac[N], sz, cnt; //多组输入注意初始化cnt = 0
    inline ll mul(ll a, ll b, ll mod) {          //WA了尝试改为__int128或慢速乘
        if (mod <= 1000000000)
            return a * b % mod;
        return (a * b - (ll)((long double)a / mod * b + 1e-8) * mod + mod) % mod;
    }
    void init(int maxn) {
        int tot = 0;
        sz = maxn - 1;
        for (int i = 1; i <= sz; ++i)
            p[i] = i;
        for (int i = 2; i <= sz; ++i) {
            if (p[i] == i)
                prime[tot++] = i;
            for (int j = 0; j < tot && 1ll * i * prime[j] <= sz; ++j) {
                p[i * prime[j]] = prime[j];
                if (i % prime[j] == 0)
                    break;
            }
        }
    }
    ll qpow(ll a, ll x, ll mod) {
        ll res = 1ll;
        while (x) {
            if (x & 1)
                res = mul(res, a, mod);
            a = mul(a, a, mod);
            x >>= 1;
        }
        return res;
    }
    bool check(ll a, ll n) {                     //二次探测原理检验n
        ll t = 0, u = n - 1;
        while (!(u & 1)){t++; u >>= 1;}
        ll x = qpow(a, u, n), xx = 0;
        while (t--) {
            xx = mul(x, x, n);
            if (xx == 1 && x != 1 && x != n - 1)
                return false;
            x = xx;
        }
        return xx == 1;
    }
    bool miller(ll n, int k) {
        if (n == 2)
            return true;
        if (n < 2 || !(n & 1))
            return false;
        if (n <= sz)
            return p[n] == n;
        for (int i = 0; i <= k; ++i) {            //测试k次
            if (!check(rand() % (n - 1) + 1, n))
                return false;
        }
        return true;
    }
    inline ll gcd(ll a, ll b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    inline ll Abs(ll x) {
        return x < 0 ? -x : x;
    }
    ll Pollard_rho(ll n) {                 //基于路径倍增的Pollard_Rho算法
        ll s = 0, t = 0, c = rand() % (n - 1) + 1, v = 1, ed = 1;
        while (1) {
            for (int i = 1; i <= ed; ++i) {
                t = (mul(t, t, n) + c) % n;
                v = mul(v, Abs(t - s), n);
                if (i % 127 == 0) {
                    ll d = gcd(v, n);
                    if (d > 1)
                        return d;
                }
            }
            ll d = gcd(v, n);

            if (d > 1)
                return d;
            s = t;
            v = 1;
            ed <<= 1;
        }
    }
    void getfactor(ll n) {                         //得到所有的质因子(可能有重复的)
        if (n <= sz) {
            while (n != 1){fac[cnt ++ ] = p[n]; n /= p[n];}
//            max_factor = max_factor > p[n] ? max_factor : p[n];
            return;
        }
        if (miller(n, 6)) {
            fac[cnt ++ ] = n;
//            max_factor = max_factor > n ? max_factor : n;
        }
        else {
            ll d = n;
            while (d >= n)
                d = Pollard_rho(n);
            getfactor(d);
            getfactor(n / d);
        }
        return ;
    }
    ll cal(ll n, ll x) {//计算 n! 中质因子 x 的数量
        ll num = 0;
        while (n) {
            num += n / x;
            n = n / x;
        }
        return num;
    }
    ll getans(ll n, ll x, ll y){
        ll ans = 4e18;
        cnt = 0;
        getfactor(x);
        map<ll, ll>mp;
        for(int i = 0; i < cnt; ++i)++mp[fac[i]];
        map<ll, ll>::iterator it;
        for(it = mp.begin(); it != mp.end(); ++it){
            ll num = 0;
            for(int i = 1; i <= n; ++i){
                num += cal(tr[i], it->first);
            }
            ans = min(ans, (cal(y, it->first) - num) / it->second);
        }
        return ans;
    }
    
    
} Q;
int main() {
    ll T, n;
    cin>>T;
    while (T--) {
        cin>>n>>x>>y;
        rep(i, 1, n)cin>>tr[i];
        cout<<Q.getans(n, x, y)<<endl;
    }
    return 0;
}

特殊的结论

• n最多仅有一个大于$\sqrt{n}$的质因子
• $p|((p-1)!+1)$,p是素数
• $((n+1)(n+2)...(n+k))$%k!=0