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

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

推荐阅读

tree
Weight the Tree（树形dp）

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

蜡笔小新 2024-12-26 15:55:56
process
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
stream
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新 2024-12-25 17:47:23
stream
图论问题解析：POJ2762 从u到v或从v到u的可达性判断（强连通分量缩点与单向连通性检测）

本文深入探讨了POJ2762问题，旨在通过强连通分量缩点和单向连通性的判断方法，解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤，并附带完整的代码示例。 ... [详细]

蜡笔小新 2024-12-24 10:44:24
stream
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
sum
丽江客栈选择问题

本文介绍了一道经典的算法题，题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈，并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]

蜡笔小新 2024-12-22 20:15:25
settings
golang常用库：配置文件解析库/管理工具viper使用

golang常用库：配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库，是由大神SteveFrancia开发，他在google领导着golang的 ... [详细]

蜡笔小新 2024-12-28 13:47:52
settings
优化ListView性能

本文深入探讨了如何通过多种技术手段优化ListView的性能，包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]

蜡笔小新 2024-12-28 10:36:30
settings
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
require
网络链路质量监控：Smokeping部署与配置

本文详细介绍了如何在Linux系统上安装和配置Smokeping，以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装，确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]

蜡笔小新 2024-12-27 19:31:05
import
Java并发编程：LinkedBlockingQueue的实际应用

本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]

蜡笔小新 2024-12-27 18:51:49
merge
Java面试题解析

本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]

蜡笔小新 2024-12-27 13:55:14
merge
Tetris 排名系统 (拓扑排序与并查集的应用)

本题旨在通过给定的评级信息，利用拓扑排序和并查集算法来确定全球 Tetris 高手排行榜。题目要求判断是否可以根据提供的信息生成一个明确的排名表，或者是否存在冲突或信息不足的情况。 ... [详细]

蜡笔小新 2024-12-24 21:03:51
merge
递推算法与大数处理

本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数，并使用递推算法和大数处理技术来解决这一问题。 ... [详细]

蜡笔小新 2024-12-23 12:18:55
merge
由二叉树到贪心算法

二叉树很重要树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。单就面试而言，在 ... [详细]

蜡笔小新 2024-12-21 13:13:13

壹滒_918

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

Tags | 热门标签

RankList | 热门文章