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

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

推荐阅读

main
洛谷 P4116 树上操作：颜色变换与路径查询

本题涉及一棵由N个节点组成的树（共有N-1条边），初始时所有节点均为白色。题目要求处理两种操作：一是改变某个节点的颜色（从白变黑或从黑变白）；二是查询从根节点到指定节点路径上的第一个黑色节点，若无则输出-1。 ... [详细]

蜡笔小新 2024-12-26 10:22:20
main
Java中访问器与修改器的深入解析

本文详细介绍了Java中的访问器（getter）和修改器（setter），探讨了它们在保护数据完整性、增强代码可维护性方面的重要作用。通过具体示例，展示了如何正确使用这些方法来控制类属性的访问和更新。 ... [详细]

蜡笔小新 2024-12-26 17:25:24
main
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
heap
MySQL索引详解与优化

本文深入探讨了MySQL中的索引机制，包括索引的基本概念、优势与劣势、分类及其实现原理，并详细介绍了索引的使用场景和优化技巧。通过具体示例，帮助读者更好地理解和应用索引以提升数据库性能。 ... [详细]

蜡笔小新 2024-12-25 19:52:47
main
寻找满足特定条件的整数N的最大和(a+b)

本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]

蜡笔小新 2024-12-26 19:26:18
main
Apache Jena 中 Txn.executeWrite 方法详解与代码示例

本文详细介绍了 Apache Jena 库中的 Txn.executeWrite 方法，通过多个实际代码示例展示了其在不同场景下的应用，帮助开发者更好地理解和使用该方法。 ... [详细]

蜡笔小新 2024-12-26 17:55:52
main
解析JSON格式文本并处理数据

本文介绍如何使用阿里云的fastjson库解析包含时间戳、IP地址和参数等信息的JSON格式文本，并进行数据处理和保存。 ... [详细]

蜡笔小新 2024-12-26 16:06:09
rsa
图数据库中的知识表示与推理机制

本文探讨了图数据库及其技术生态系统在知识表示和推理问题上的应用。通过理解图数据结构，尤其是属性图的特性，可以为复杂的数据关系提供高效且优雅的解决方案。我们将详细介绍属性图的基本概念、对象建模、概念建模以及自动推理的过程，并结合实际代码示例进行说明。 ... [详细]

蜡笔小新 2024-12-26 12:11:47
rsa
使用JPA Criteria API构建动态查询条件

本文介绍如何使用JPA Criteria API创建带有多个可选参数的动态查询方法。当某些参数为空时，这些参数不会影响最终查询结果。 ... [详细]

蜡笔小新 2024-12-26 09:26:16
main
Python文本处理与可视化：分词及词云生成

本文介绍如何使用Python进行文本处理，包括分词和生成词云图。通过整合多个文本文件、去除停用词并生成词云图，展示文本数据的可视化分析方法。 ... [详细]

蜡笔小新 2024-12-26 08:37:18
main
并发编程：深入理解设计原理与优化

本文探讨了并发编程中的关键设计原则，特别是Java内存模型（JMM）的happens-before规则及其对多线程编程的影响。文章详细介绍了DCL双重检查锁定模式的问题及解决方案，并总结了不同处理器和内存模型之间的关系，旨在为程序员提供更深入的理解和最佳实践。 ... [详细]

蜡笔小新 2024-12-26 01:14:06
function
基于KVM的SRIOV直通配置及性能测试

SRIOV介绍、VF直通配置，以及包转发率性能测试小慢哥的原创文章，欢迎转载目录?1.SRIOV介绍?2.环境说明?3.开启SRIOV?4.生成VF?5.VF ... [详细]

蜡笔小新 2024-12-25 19:26:39
function
魔兽世界：备战策略

本文探讨了《魔兽世界》中红蓝两方阵营在备战阶段的策略与实现方法，通过代码展示了双方如何根据资源和兵种特性进行战士生产。 ... [详细]

蜡笔小新 2024-12-25 19:03:01
main
Codeforces Round #566 (Div. 2) A~F个人题解

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]

蜡笔小新 2024-12-25 18:41:21
main
GDI基础介绍之几何绘图

使用GDI的一些AIP函数我们可以轻易的绘制出简 ... [详细]

蜡笔小新 2024-12-25 18:23:37

壹滒_918

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

Tags | 热门标签

RankList | 热门文章