2019icpc徐州 E题 Multiply(pollard_rho)

样例输入复制

样例输出复制

2
8

O(1) 快速乘你能秒我？？

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <time.h>
#include <random>

typedef long long LL;
using namespace std;

int t, n;
LL x, y, a[100005];
mt19937 rd(time(0));

LL ksm(LL a, LL b, LL mod){
    return (a * b - (LL)((long double)a / mod * b) * mod + mod) % mod;
}

LL poww(LL x, LL num, LL mod){
    LL res = 1;
    x %= mod;
    while(num){
        if(num & 1) res = ksm(res, x, mod);
        x = ksm(x, x, mod);
        num >>= 1;
    }
    return res;
}

struct Mill{
    
    LL n, fac[22000][2], bk[22000]; int tot;

    const int C = 2307;
    const int S = 8;

    bool check(LL a, LL n){
        LL m = n - 1, x, y = 0;
        int j = 0;
        while (!(m & 1)) m >>= 1, j++;
        x = poww(a, m, n);
        for (int i = 1; i <= j; x = y, i++){
            y = ksm(x, x, n);
            if (y == 1 && x != 1 && x != n - 1) return 1;
        }
        return y != 1;
    }

    bool miller_rabin(LL n){
        if(n < 2){
            return 0;
        }else if (n == 2){
            return 1;
        }else if (!(n & 1)){
            return 0;
        }
        for (int i = 0; i < S; ++i){
            if (check(rd() % (n - 1) + 1, n)) return 0;
        }
        return 1;
    }

    LL pollard_rho(LL n, int c){
        LL i = 1, k = 2, x = rd() % n, y = x, d;
        while (1) {
            ++i; x = (ksm(x, x, n) + c) % n;
            d = __gcd(y - x, n);
            if(d > 1 && d < n){
                return d;
            }
            if(y == x){
                return n;
            }
            if(i == k){
                y = x;
                k <<= 1;
            }
        }
    }

    void findfac(LL n, int c){
        if(n == 1){
            return ;
        }
        if(miller_rabin(n)){
            bk[++*bk] = n;
            return ;
        }
        LL m = n;
        while(m == n){
            m = pollard_rho(n, c--);
        }
        findfac(m, c);
        findfac(n / m, c);
    }
    void gao(LL _n){
        n = _n; *bk = 0;
        findfac(n, C);
        sort(bk + 1, bk + 1 + *bk);
        fac[1][0] = bk[1];
        fac[1][1] = 1;
        tot = 1;
        for (int i = 2; i <= *bk; i++){
            if (bk[i] == bk[i - 1]) {
                ++fac[tot][1];
            }else{
                ++tot;
                fac[tot][0] = bk[i];
                fac[tot][1] = 1;
            }
        }
    }

}mill;

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    scanf("%d", &t);
    while(t--){
        scanf("%d %lld %lld", &n, &x, &y);
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        mill.gao(x);
        LL ans = 1LL << 60;
        for (int i = 1; i <= mill.tot; i++){
            LL nu = 0, tp, w;
            // printf("%lld %lld\n", fac[i], num[i]);
            for (int j = 1; j <= n; j++){
                tp = log(a[j]) / log(mill.fac[i][0]);
                w = 1;
                for (int k = 1; k <= tp; k++) w *= mill.fac[i][0], nu += a[j] / w;
            }
            w = 1;
            tp = log(y) / log(mill.fac[i][0]);
            for (int k = 1; k <= tp; k++) w *= mill.fac[i][0], nu -= y / w;
            // printf("%lld %lld\n", fac[i], tp);
            nu = max(0LL, -nu);
            ans = min(ans, nu / mill.fac[i][1]);
        }
        printf("%lld\n", ans);
    }

    return 0;
}
/**/