当前位置: 开发笔记 > 编程语言 > 正文

DiscreteLogging(POJ2417+BSGS)

作者：壹滒_918 | 来源：互联网 | 2023-10-12 15:57

题目链接：http:poj.orgproblem?id2417题目：题意：求一个最小的x满足a^xb(modp)，p为质数。

题目链接&＃xff1a;http://poj.org/problem?id&＃61;2417

题目&＃xff1a;

题意&＃xff1a;

　　求一个最小的x满足a^x&＃61;&＃61;b(mod p)&＃xff0c;p为质数。

思路&＃xff1a;

　　BSGS板子题&＃xff0c;推荐一篇好的BSGS和扩展BSGS的讲解博客&＃xff1a;http://blog.miskcoo.com/2015/05/discrete-logarithm-problem

代码实现如下&＃xff1a;

1 #include <set>
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include <string>
9 #include
10 #include
11 #include
12 #include
13 #include
14 using namespace std;
15
16 typedef long long LL;
17 typedef pair pLL;
18 typedef pairint> pli;
19 typedef pair<int, LL> pil;;
20 typedef pair<int, int> pii;
21 typedef unsigned long long uLL;
22
23 #define lson i<<1
24 #define rson i<<1|1
25 #define lowbit(x) x&(-x)
26 #define bug printf("*********\n");
27 #define debug(x) cout<<"["< 28 #define FIN freopen("D://code//in.txt", "r", stdin);
29 #define IO ios::sync_with_stdio(false),cin.tie(0);
30
31 const double eps &＃61; 1e-8;
32 const int mod &＃61; 1e9 &＃43; 7;
33 const int maxn &＃61; 1e6 &＃43; 7;
34 const double pi &＃61; acos(-1);
35 const int inf &＃61; 0x3f3f3f3f;
36 const LL INF &＃61; 0x3f3f3f3f3f3f3f3f;
37
38 int a, b, p;
39
40 struct Hashmap { //哈希表
41 static const int Ha&＃61;999917, maxe&＃61;46340;
42 int E,lnk[Ha], son[maxe&＃43;5], nxt[maxe&＃43;5], w[maxe&＃43;5];
43 int top, stk[maxe&＃43;5];
44 void clear() {
45 E&＃61;0;
46 while(top) lnk[stk[top--]]&＃61;0;
47 }
48 void Add(int x,int y) {
49 son[&＃43;&＃43;E]&＃61;y;
50 nxt[E]&＃61;lnk[x];
51 w[E]&＃61;((1<<30) - 1) * 2 &＃43; 1;
52 lnk[x]&＃61;E;
53 }
54 bool count(int y) {
55 int x&＃61;y % Ha;
56 for (int j &＃61; lnk[x]; j; j&＃61;nxt[j])
57 if (y &＃61;&＃61; son[j]) return true;
58 return false;
59 }
60 int& operator [] (int y) {
61 int x&＃61;y % Ha;
62 for (int j &＃61; lnk[x]; j; j &＃61; nxt[j])
63 if (y &＃61;&＃61; son[j]) return w[j];
64 Add(x,y);
65 stk[&＃43;&＃43;top]&＃61;x;
66 return w[E];
67 }
68 }mp;
69
70 int exgcd(int a, int b, int& x, int& y) {
71 if(b &＃61;&＃61; 0) {
72 x &＃61; 1, y &＃61; 0;
73 return a;
74 }
75 int d &＃61; exgcd(b, a % b, x, y);
76 int t &＃61; x;
77 x &＃61; y;
78 y &＃61; t - a / b * y;
79 return d;
80 }
81
82 int BSGS(int A, int B, int C) {
83 if(C &＃61;&＃61; 1) {
84 if(!B) return A !&＃61; 1;
85 else return -1;
86 }
87 if(B &＃61;&＃61; 1) {
88 if(A) return 0;
89 else return -1;
90 }
91 if(A % C &＃61;&＃61; 0) {
92 if(!B) return 1;
93 else return -1;
94 }
95 int m &＃61; ceil(sqrt(C)); //分块
96 int D &＃61; 1, base &＃61; 1;
97 mp.clear();
98 for(int i &＃61; 0; i <&＃61; m - 1; i&＃43;&＃43;) {
99 if(mp[base] &＃61;&＃61; 0) mp[base] &＃61; i;
100 else mp[base] &＃61; min(mp[base], i);
101 base &＃61; ((LL)base * A) % C;
102 }
103 for(int i &＃61; 0; i <&＃61; m - 1; i&＃43;&＃43;) {
104 int x, y, d &＃61; exgcd(D, C, x, y);
105 x &＃61; ((LL)x * B % C &＃43; C) % C;
106 if(mp.count(x)) return i * m &＃43; mp[x];
107 D &＃61; ((LL)D * base) % C;
108 }
109 return -1;
110 }
111
112 int main() {
113 //FIN;
114 while(~scanf("%d%d%d", &p, &a, &b)) {
115 int ans &＃61; BSGS(a, b, p);
116 if(ans &＃61;&＃61; -1) printf("no solution\n");
117 else printf("%d\n", ans);
118 }
119 return 0;
120 }

转载于:https://www.cnblogs.com/Dillonh/p/9511118.html

推荐阅读

case
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
case
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
include
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
java
Java学习笔记之面向对象编程（OOP）

本文介绍了Java学习笔记中的面向对象编程（OOP）内容，包括OOP的三大特性（封装、继承、多态）和五大原则（单一职责原则、开放封闭原则、里式替换原则、依赖倒置原则）。通过学习OOP，可以提高代码复用性、拓展性和安全性。 ... [详细]

蜡笔小新 2023-12-13 08:44:30
request
深入理解Kafka服务端请求队列中请求的处理

本文深入分析了Kafka服务端请求队列中请求的处理过程，详细介绍了请求的封装和放入请求队列的过程，以及处理请求的线程池的创建和容量设置。通过场景分析、图示说明和源码分析，帮助读者更好地理解Kafka服务端的工作原理。 ... [详细]

蜡笔小新 2023-12-12 16:14:59
function
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

蜡笔小新 2023-12-12 14:05:58
char
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
byte
java boolean 大小_java boolean 大小

先看官方文档TheJavaTutorialshavebeenwrittenforJDK8.Examplesandpracticesdescribedinthispagedontta ... [详细]

蜡笔小新 2023-12-12 13:36:56
char
Which is more efficient: char str[] or char *str?

This article discusses the efficiency of using char str[] and char *str and whether there is any reason to prefer one over the other. It explains the difference between the two and provides an example to illustrate their usage. ... [详细]

蜡笔小新 2023-12-12 10:13:35
java
Java太阳系小游戏分析和源码详解

本文介绍了一个基于Java的太阳系小游戏的分析和源码详解。通过对面向对象的知识的学习和实践，作者实现了太阳系各行星绕太阳转的效果。文章详细介绍了游戏的设计思路和源码结构，包括工具类、常量、图片加载、面板等。通过这个小游戏的制作，读者可以巩固和应用所学的知识，如类的继承、方法的重载与重写、多态和封装等。 ... [详细]

蜡笔小新 2023-12-14 19:53:34
char
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
include
UVALive6575 Odd and Even Zeroes 数位dp+找规律

本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]

蜡笔小新 2023-12-13 14:19:28
char
C++字符字符串处理及字符集编码方案

本文介绍了C++中字符字符串处理的问题，并详细解释了字符集编码方案，包括UNICODE、Windows apps采用的UTF-16编码、ASCII、SBCS和DBCS编码方案。同时说明了ANSI C标准和Windows中的字符/字符串数据类型实现。文章还提到了在编译时需要定义UNICODE宏以支持unicode编码，否则将使用windows code page编译。最后，给出了相关的头文件和数据类型定义。 ... [详细]

蜡笔小新 2023-12-13 04:59:58
triggers
引擎之旅 Chapter.2 线程库

预备知识可参考我整理的博客Windows编程之线程:https:www.cnblogs.comZhuSenlinp16662075.htmlWindows编程之线程同步:https ... [详细]

蜡笔小新 2023-12-12 14:06:39
java
JDK源码学习之HashTable(附带面试题)的学习笔记

本文介绍了JDK源码学习之HashTable(附带面试题)的学习笔记，包括HashTable的定义、数据类型、与HashMap的关系和区别。文章提供了干货，并附带了其他相关主题的学习笔记。 ... [详细]

蜡笔小新 2023-12-12 13:05:17

壹滒_918

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章