文档章节

BZOJ5296 [CQOI2018] 破解D-H协议 【数学】【BSGS】

o
 osc_z1hvg4cu
发布于 2018/04/24 21:59
字数 272
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目分析:

  裸题。

代码:

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 
 6 const int BASE = 10045601;
 7 
 8 #define mp make_pair
 9 
10 ll g,p;
11 ll srt = 50000;
12 vector<pair<int,ll> > hash[10200000];
13 
14 ll fast_pow(ll now,ll pw){
15     if(pw == 1) return now;
16     ll z = fast_pow(now,pw/2);
17     z *= z ; z %= p;
18     if(pw & 1)z *= now,z %= p;
19     return z;
20 }
21 
22 void CreatHash(){
23     ll xm = fast_pow(g,srt);
24     ll hh = xm;
25     for(ll i=1;(i-1)*srt<=INT_MAX;i++,hh = (hh*xm)%p){
26     hash[hh % BASE].push_back(mp(i,hh));
27     }
28 }
29 
30 void read(){
31     scanf("%lld%lld",&g,&p);
32     CreatHash();
33 }
34 
35 ll solve(ll now){
36     ll hh = g;
37     for(int i=1;i<=50000;i++,hh=(hh*g)%p){
38     ll nowp = (hh*now)%p;
39     for(int j=0;j<hash[nowp%BASE].size();j++){
40         ll out = hash[nowp%BASE][j].second;
41         if(out == nowp){
42         out = hash[nowp%BASE][j].first;
43         return out*srt-i;
44         }
45     }
46     }
47 }
48 
49 void work(){
50     int n;scanf("%d",&n);
51     for(int i=1;i<=n;i++){
52     ll a,b; scanf("%lld%lld",&a,&b);
53     ll hh = solve(a);
54     ll key = fast_pow(b,hh);
55     printf("%lld\n",key);
56     }
57 }
58 
59 int main(){
60     read();
61     work();
62     return 0;
63 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Spark Summit North America 202006 高清 PPT 下载

为期五天的 Spark Summit North America 2020在美国时间 2020-06-22 ~ 06-26 举行。由于今年新冠肺炎的影响,本次会议第一次以线上的形式进行。这次会议虽然是五天,但是前两天是培训,后面三...

osc_z9t307rr
1分钟前
0
0
矩阵计算与AI革命:可将计算性能提高150倍的异构计算

本文翻译自Wikibon矩阵计算与AI革命系列研究文章。 如今异构计算(Heterogeneous Compute,HC)已经部署在消费类移动设备中,与传统架构相比可以将矩阵工作负载的性能提高50倍。同时,这也将...

osc_ml6lx2h4
2分钟前
0
0
smart 后台 使用说明

乐观锁 说明 如果想实现如下需求: 当要更新一条记录的时候,希望这条记录没有被别人更新,确保当前只有一个人在操作。 乐观锁的实现原理: 取出记录时,获取当前 version 2 更新时,带上这个 ...

奔跑的android
3分钟前
0
0
关于win10的hype-v与VMWARE启动冲突的解决方法

升级win10后,在卸载hype-v重启电脑后仍然报错,解决的办法是只需要直接使用管理员身份打命令提示符,然后执行以下命令即可: bcdedit /set hypervisorlaunchtype off...

osc_l7zl78wt
4分钟前
0
0
操作系统设计中的加电引导

作者:丁宋涛 系统启动过程概述 在掀下电脑开机按钮后,电源就会开始向主板和其他外围设备供电。初始状态下的电压还不太稳定,因此并不会立即开始指令的执行。此时,主板上的控制芯片组会发出重...

osc_kz2s8mnr
6分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部