POJ2417 Baby-Step-Gaint-Step 算法
发布日期:2022-02-07 06:39:33 浏览次数:11 分类:技术文章

本文共 2124 字,大约阅读时间需要 7 分钟。

考虑一个问题:A^x%p=B,给定A,B,p,求x的最小非负整数解。

在p是质数的情况下,这个问题比较简单。

A^x=B(mod P) (P is a Prime, A,B
if A^i=A^j(i
Enumerate i, Let x=i*m+j, A^(i*m)*A^j=B(mod C)Let E=A^(i*m),F=A^j,E*F=B(mod P) because (E,C)=1,(E,C)|B,we can use EXTgcd to get F.
If F is in the HashSet,then the minimum answer x=i*m+M[F].
Because P is a Prime, and A,B
So the range of i is [0,P/m].
If for all i we cannot find a answer, then no solution.
 我亲手胡乱写的东西,能看懂才怪! 

再附上代码吧:(我的小数据范围是暴力的)

#include 
#include
#include
#include
#include
#include
using namespace std;typedef long long LL;inline void Exgcd(LL a, LL b, LL &d, LL &x, LL &y) { if (!b) { d = a, x = 1, y = 0; } else { Exgcd(b, a % b, d, y, x), y -= x * (a / b); }}inline LL gcd(LL a, LL b) { return (!b) ? a : gcd(b, a % b);}inline LL Solve(LL a, LL b, LL c) { // ax=b(mod c) LL d, x, y; Exgcd(a, c, d, x, y); return (x + c) % c * b % c;}LL ksm(LL x, LL y, LL p) { LL res = 1, t = x; for(; y; y >>= 1) { if (y & 1) res = res * t % p; t = t * t % p; } return res;}const int mod = 13131;struct Hashset { int head[mod], next[40010], f[40010], v[40010], ind; void reset() { ind = 0; memset(head, -1, sizeof head); } void insert(int x, int _v) { int ins = x % mod; for(int j = head[ins]; j != -1; j = next[j]) if (f[j] == x) { v[j] = min(v[j], _v); return; } f[ind] = x, v[ind] = _v; next[ind] = head[ins], head[ins] = ind++; } int operator [] (const int &x) const { int ins = x % mod; for(int j = head[ins]; j != -1; j = next[j]) if (f[j] == x) return v[j]; return -1; }}S;int main() { LL A, B, C; LL i; while(scanf("%I64d%I64d%I64d", &C, &A, &B) == 3) { if (C <= 100) { LL d = 1; bool find = 0; for(i = 0; i < C; ++i) { if (d == B) { find = 1; printf("%I64d\n", i); break; } d = d * A % C; } if (!find) puts("no solution"); } else { int m = (int)sqrt(C); S.reset(); LL d = 1; for(i = 0; i < m; ++i) { S.insert(d, i); d = d * A % C; } bool find = 0; int ins; for(i = 0; i * m < C; ++i) { LL t = Solve(ksm(A, i * m, C), B, C); if ((ins = S[t]) != -1) { printf("%I64d\n", i * m + ins); find = 1; break; } } if (!find) puts("no solution"); } } return 0;}

转载地址:https://blog.csdn.net/wyfcyx_forever/article/details/40538515 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:BZOJ3786 星系探索 蒟蒻出题人给跪
下一篇:POJ3243 EXT-BSGS算法

发表评论

最新留言

很好
[***.229.124.182]2024年02月29日 20时33分57秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

vscode 不能使用中文输入法_vscode中vim插件设置 2021-06-24
的流程图做完后如何保存_2019超火的半永久眉是哪款?做完后我们如何护理?... 2021-06-24
去除logo 高德地图api_深圳品牌logo升级如何保持原型的同时更具创新? 2021-06-24
二重积分转换成极坐标_二重积分转换极坐标r的范围如何确定? 2021-06-24
npm 不重启 全局安装后_解决修复npm安装全局模块权限的问题 2021-06-24
vs格式化json 不生效_vs code 格式化 json 配置 2021-06-24
go 字符串反序列化成对象数组_Fastjson 1.2.24反序列化漏洞深度分析 2021-06-24
onmessage websocket 收不到信息_WebSocket断开重连解决方案,心跳重连实践 2021-06-24
hibernate mysql 缓存_hibernate和mysql的缓存问题,没辙了! 2021-06-24
abp框架 mysql_ABP框架使用Mysql数据库 2021-06-24
android组件动态接收数据库,Android开发——fragment中数据传递与刷新UI(更改控件)... 2021-06-24
云麦小米华为体脂秤怎么样_云康宝和华为智能体脂秤对比评测,实际体验告诉你哪款更好... 2021-06-24
修改表格字体颜色_Excel技巧:Excel如何修改字体颜色 2021-06-24
native react 变颜色 点击_React Native主动更改StackNavigator标头颜色 2021-06-24
prism项目搭建 wpf_WPF MVVM使用prism4.1搭建 2021-06-24
python发微信红包群_用Python实现微信自动化抢红包,再也不用担心抢不到红包了... 2021-06-24
python中func自定义函数_Python函数之自定义函数&作用域&闭包 2021-06-24
wget连接指定端口_端口通不通 telnet wget ssh 2021-06-24
eureka 调用服务_Spring Cloud微服务架构从入门到会用(二)—服务注册中心Eureka... 2021-06-24
easyexcel 工具类_问了个在阿里的同学,他们常用的15款开发者工具! 2021-06-24