2019icpc徐州 E题 Multiply(pollard_rho)
发布时间
阅读量：
阅读量
样例输入复制
2
3 10 10
2 3 4
2 2 10
1 1
AI写代码样例输出复制
2
8
AI写代码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;
}
/**/
AI写代码全部评论 (0)
还没有任何评论哟~