2019icpc徐州 E题 Multiply(pollard_rho)

样例输入复制

2
3 10 10
2 3 4
2 2 10
1 1

样例输出复制

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;
}
/**/

 

 

全部评论

相关推荐

点赞 评论 收藏
分享
05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
投递美团等公司10个岗位
点赞 评论 收藏
分享
Java抽象带篮子:简历怎么写可以看看我发的帖子,你的第一个是实习经历吗?那怎么写的是你的第一个练手项目呢?简历写的怎么样直接投小厂面试一下就知道了
没有实习经历,还有机会进...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务