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

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

推荐阅读

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

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

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

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

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

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

蜡笔小新 2023-12-13 19:52:19
stream
开发笔记：实验7的文件读写操作

本文介绍了使用C++的ofstream和ifstream类进行文件读写操作的方法，包括创建文件、写入文件和读取文件的过程。同时还介绍了如何判断文件是否成功打开和关闭文件的方法。通过本文的学习，读者可以了解如何在C++中进行文件读写操作。 ... [详细]

蜡笔小新 2023-12-12 17:48:18
future
伊振华作品 | 沈阳市智慧城市运行管理中心的设计与建设

本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计，并以数字赋能和创新驱动高质量发展的理念，建设了集成、智慧、高效的一体化城市综合管理平台，促进了城市的数字化转型。该中心被称为当代城市的智能心脏，为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]

蜡笔小新 2023-12-14 16:35:39
php
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
char
油田地块的划分和计数方法

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

蜡笔小新 2023-12-14 09:18:20
char
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
input
UVALive6575 Odd and Even Zeroes 数位dp+找规律

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

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

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

蜡笔小新 2023-12-13 08:44:30
char
clone的fork与pthread_create创建线程有何不同

本文讨论了clone的fork与pthread_create创建线程的不同之处。进程是一个指令执行流及其执行环境，其执行环境是一个系统资源的集合。在调用系统调用fork创建一个进程时，子进程只是完全复制父进程的资源，这样得到的子进程独立于父进程，具有良好的并发性。但是二者之间的通讯需要通过专门的通讯机制，另外通过fork创建子进程系统开销很大。因此，在某些情况下，使用clone或pthread_create创建线程可能更加高效。 ... [详细]

蜡笔小新 2023-12-12 20:00:06
sum
hdu 5439（找规律）的数列求和问题

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

蜡笔小新 2023-12-12 14:05:58
input
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
require
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
require
引擎之旅 Chapter.2 线程库

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

蜡笔小新 2023-12-12 14:06:39

壹滒_918

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

Tags | 热门标签

RankList | 热门文章