poj2417bsgs算法，用于求解A^x=B(modC)的方程

作者：夜沙 | 来源：互联网 | 2023-01-31 21:54

*给定A,B,C,C是质数，求出A^xB(modC)的解解：A^xA^(x%phi[C])B(modC)(欧拉定理推论)x%phi[C]

/*
给定A,B,C,C是质数，求出A^x=B(mod C)的解
解：A^x = A^(x % phi[C]) = B(mod C) (欧拉定理推论)
x % phi[C] 所以不超过C的范围内必有一个解，
只要求到C即可，
进行分块，另 m=sqrt(C),向上取整,
那么 x=i*m-j
原式==》A^j*B = A^(m*i)(mod C)
先枚举j，将A^j*B进行hash
再枚举i，从hash表中找到第一个满足条件的A^j*B
此时x=i*m-j
*/
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
ll a,b,c,m,f[10000000];
mapmp;
ll Pow(ll x){
ll res=1,aa=a;
while(x>0){
if(x%2)
res=res*aa%c;
x>>=1;
aa=aa*aa%c;
}
return res;
}
int main(){
while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF){
mp.clear();
if(a%c==0){//c|a,显然是不存在解x的，除非
puts("no solution");
continue;
}
int p=0;
m=ceil(sqrt(c*1.0));
ll ans;

for(int j=0;j<=m;j++){//预处理所有j的情况，建立hash表
if(j==0){
ans=b%c;mp[ans]=j;continue;
}
ans=(ans*a)%c;
mp[ans]=j;
}

ll t=Pow(m);
ans=1;
for(int i=1;i<=m;i++){
ans=(ans*t)%c;
if(mp[ans]){//枚举每个块ans=a^(m*i)=a^j*b,把hash表中的那个j找到即可
int t=i*m-mp[ans];
printf("%d\n",(t%c+c)%c);
p=1;
break;
}
}
if(!p)
puts("no solution");
}
}

推荐阅读

include
Codeforces 1294A题解：Collecting Coins整除+不整除问题解析

本文为Codeforces 1294A题目的解析，主要讨论了Collecting Coins整除+不整除问题。文章详细介绍了题目的背景和要求，并给出了解题思路和代码实现。同时提供了在线测评地址和相关参考链接。 ... [详细]

蜡笔小新 2023-12-14 21:14:58
include
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
include
九度OnlineJudge之1002：Grading问题的解决方法

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

蜡笔小新 2023-12-14 13:00:09
include
C++省略号类型和参数个数不确定函数参数范例

本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法，并提供了一个范例。通过宏定义的方式，可以方便地处理不定参数的情况。文章中给出了具体的代码实现，并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说，是一个很有用的参考资料。 ... [详细]

蜡笔小新 2023-12-14 12:36:28
include
Open judge C16H: Magical Balls 快速幂+逆元问题解析

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

蜡笔小新 2023-12-14 12:03:27
include
差分约束系统求解House Man跳跃问题的思路与方法

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

蜡笔小新 2023-12-14 11:49:51
include
c语言\n不换行,c语言printf不换行

$c语言\n不换行,c语言printf不换行$

本文目录一览：1、C语言不换行输入2、c语言的 ... [详细]

蜡笔小新 2023-12-14 11:05:35
include
油田地块的划分和计数方法

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

蜡笔小新 2023-12-14 09:18:20
include
P1651 塔 (动态规划) 的最大高度计算方法

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

蜡笔小新 2023-12-13 19:52:19
include
二叉树层序创建问题的解决方法

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

蜡笔小新 2023-12-13 18:20:50
include
C函数ispunct()的用法及示例代码

本文介绍了C函数ispunct()的用法及示例代码。ispunct()函数用于检查传递的字符是否是标点符号，如果是标点符号则返回非零值，否则返回零。示例代码演示了如何使用ispunct()函数来判断字符是否为标点符号。 ... [详细]

蜡笔小新 2023-12-13 18:13:34
include
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
include
UVALive6575 Odd and Even Zeroes 数位dp+找规律

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

蜡笔小新 2023-12-13 14:19:28
include
Linux环境变量函数getenv、putenv、setenv和unsetenv详解

本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数，可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值，并打印出来。 ... [详细]

蜡笔小新 2023-12-13 12:01:03
dll
PE总结9PE文件结构之解析导出表

本文介绍了PE文件结构中的导出表的解析方法，包括获取区段头表、遍历查找所在的区段等步骤。通过该方法可以准确地解析PE文件中的导出表信息。 ... [详细]

蜡笔小新 2023-12-13 11:47:24

夜沙

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

Tags | 热门标签

RankList | 热门文章