Discrete Logging(POJ2417 + BSGS)

时间:2022-10-23 21:10:21

题目链接:http://poj.org/problem?id=2417

题目:

Discrete Logging(POJ2417 + BSGS)

Discrete Logging(POJ2417 + BSGS)

Discrete Logging(POJ2417 + BSGS)

题意:

  求一个最小的x满足a^x==b(mod p),p为质数。

思路:

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

代码实现如下:

 #include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL; #define lson i<<1
#define rson i<<1|1
#define lowbit(x) x&(-x)
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define FIN freopen("D://code//in.txt", "r", stdin);
#define IO ios::sync_with_stdio(false),cin.tie(0); const double eps = 1e-;
const int mod = 1e9 + ;
const int maxn = 1e6 + ;
const double pi = acos(-);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f; int a, b, p; struct Hashmap { //哈希表
static const int Ha=, maxe=;
int E,lnk[Ha], son[maxe+], nxt[maxe+], w[maxe+];
int top, stk[maxe+];
void clear() {
E=;
while(top) lnk[stk[top--]]=;
}
void Add(int x,int y) {
son[++E]=y;
nxt[E]=lnk[x];
w[E]=((<<) - ) * + ;
lnk[x]=E;
}
bool count(int y) {
int x=y % Ha;
for (int j = lnk[x]; j; j=nxt[j])
if (y == son[j]) return true;
return false;
}
int& operator [] (int y) {
int x=y % Ha;
for (int j = lnk[x]; j; j = nxt[j])
if (y == son[j]) return w[j];
Add(x,y);
stk[++top]=x;
return w[E];
}
}mp; int exgcd(int a, int b, int& x, int& y) {
if(b == ) {
x = , y = ;
return a;
}
int d = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return d;
} int BSGS(int A, int B, int C) {
if(C == ) {
if(!B) return A != ;
else return -;
}
if(B == ) {
if(A) return ;
else return -;
}
if(A % C == ) {
if(!B) return ;
else return -;
}
int m = ceil(sqrt(C)); //分块
int D = , base = ;
mp.clear();
for(int i = ; i <= m - ; i++) {
if(mp[base] == ) mp[base] = i;
else mp[base] = min(mp[base], i);
base = ((LL)base * A) % C;
}
for(int i = ; i <= m - ; i++) {
int x, y, d = exgcd(D, C, x, y);
x = ((LL)x * B % C + C) % C;
if(mp.count(x)) return i * m + mp[x];
D = ((LL)D * base) % C;
}
return -;
} int main() {
//FIN;
while(~scanf("%d%d%d", &p, &a, &b)) {
int ans = BSGS(a, b, p);
if(ans == -) printf("no solution\n");
else printf("%d\n", ans);
}
return ;
}

Discrete Logging(POJ2417 + BSGS)的更多相关文章

  1. POJ2417 Discrete Logging【BSGS】

    Discrete Logging Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 5577   Accepted: 2494 ...

  2. Discrete Logging&lpar;poj2417&rpar;

    Discrete Logging Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 5120   Accepted: 2319 ...

  3. POJ2417 Discrete Logging【BSGS】&lpar;模板题&rpar;

    <题目链接> 题目大意: P是素数,然后分别给你P,B,N三个数,然你求出满足这个式子的L的最小值 : BL== N (mod P). 解题分析: 这题是bsgs算法的模板题. #incl ...

  4. BZOJ 3239 Discrete Logging(BSGS)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=3239 [题目大意] 计算满足 Y^x ≡ Z ( mod P) 的最小非负整数 [题解 ...

  5. 【BSGS】BZOJ3239 Discrete Logging

    3239: Discrete Logging Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 729  Solved: 485[Submit][Statu ...

  6. BSGS算法&plus;逆元 POJ 2417 Discrete Logging

    POJ 2417 Discrete Logging Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 4860   Accept ...

  7. 【BZOJ3239】Discrete Logging BSGS

    [BZOJ3239]Discrete Logging Description Given a prime P, 2 <= P < 231, an integer B, 2 <= B ...

  8. BSGS 扩展大步小步法解决离散对数问题 &lpar;BZOJ 3239&colon; Discrete Logging&sol;&sol; 2480&colon; Spoj3105 Mod&rpar;

    我先转为敬? orz% miskcoo 贴板子 BZOJ 3239: Discrete Logging//2480: Spoj3105 Mod(两道题输入不同,我这里只贴了3239的代码) CODE ...

  9. &lbrack;POJ2417&rsqb;Discrete Logging(指数级同余方程)

    Discrete Logging Given a prime P, 2 <= P < 2 31, an integer B, 2 <= B < P, and an intege ...

随机推荐

  1. mysql数据库开发常见问题及优化

    mysql 数据库是被广泛应用的关系型数据库,其体积小.支持多处理器.开源并免费的特性使其在 Internet 中小型网站中的使用率尤其高.在使用 mysql 的过程中不规范的 SQL 编写.非最优的 ...

  2. &lbrack;翻译&rsqb; CBStoreHouseTransition

    CBStoreHouseTransition What is it? A custom transition inspired by Storehouse iOS app, also support ...

  3. oracle用户权限的问题

    一.创建用户 create user username identified by password --username 创建的用户的名称 --password 创建的用户的密码 二.赋权限 gra ...

  4. Linux下 输入 env 而得到的环境变量解读

    HOSTNAME=Master.Hadoop MAHOUT_HOME=/usr/hadoop/mahout-distribution-0.8 TERM=linux SHELL=/bin/bash HA ...

  5. Linked List - leetcode

    138. Copy List with Random Pointer //不从head走 前面加一个dummy node 从dummy走先连head 只需记录当前节点 //这样就不需要考虑是先new ...

  6. Linux下安装Tomcat启动报错

    一.报以下错误: Using CATALINA_BASE:   /home/apache-tomcat-7.0.72Using CATALINA_HOME:   /home/apache-tomcat ...

  7. SharePoint 2010 安装错误:请重新启动计算机,然后运行安装程序以继续

    一.环境:Windows Server 2008 R2 with sp1,SharePoint 2010 二.问题描述: 正常的安装SharePoint 2010 ,安装完必备组件,并提示所有必备组件 ...

  8. 关于js的函数

    1.获取内容的兼容函数 /* * 一: 获取内容的兼容函数 * setText(obj, str) * 思路: * 1.首先判断浏览器: * 2.如果是IE浏览器,就用innerText: * 3.如 ...

  9. Python面向对象中的classmethod类方法和&lowbar;&lowbar;getattr&lowbar;&lowbar;方法介绍

    一.classmethod介绍 介绍:@classmethod修饰符我们从名称就可以知道,这是一个类方法,那么和普通的类中的方法有什么不同的 a.类方法,是由类本身调用的,无需实例化类,直接用类本身调 ...

  10. 机器学习进阶-案例实战-答题卡识别判 1&period;cv2&period;getPerspectiveTransform&lpar;获得投射变化后的H矩阵&rpar; 2&period;cv2&period;warpPerspective&lpar;H获得变化后的图像&rpar; 3&period;cv2&period;approxPolyDP&lpar;近似轮廓&rpar; 4&period;cv2&period;threshold&lpar;二值变化&rpar; 7&period;cv2&period;countNonezeros&lpar;非零像素点个数&rpar;6&period;cv2&period;bitwise&lowbar;and&lpar;与判断&rpar;

    1.H = cv2.getPerspectiveTransform(rect, transform_axes) 获得投射变化后的H矩阵 参数说明:rect表示原始的位置左上,右上,右下,左下, tra ...