当前位置:首页 > 数学 > 正文
洛谷P4195【模板】扩展BSGS
110+

题目大意:给定 $a,p,b$,求满足 $a^x≡b \pmod p$ 的最小自然数 $x$ 。

题目背景

题目来源:SPOJ3105 Mod

题目描述

给定 $a,p,b$,求满足 $a^x≡b \pmod p$ 的最小自然数 $x$ 。

输入输出格式

输入格式

每个测试文件中最多包含 $100$ 组测试数据。

每组数据中,每行包含 $3$ 个正整数 $a,p,b$ 。

当 `a=p=b=0` 时,表示测试数据读入完全。

输出格式

对于每组数据,输出一行。

如果无解,输出`No Solution`,否则输出最小自然数解。

输入输出样例

输入样例 #1

5 58 33
2 4 3
0 0 0

输出样例 #1

9
No Solution

说明

对于 $100\%$ 的数据,$a,p,b≤10^9$。

解题思路

显然,在0~p-1中必有答案。p很大,逐一枚举会超时,我们可以采用折半枚举、双向搜索,哈希判重。

令 $x = A \left \lceil \sqrt p \right \rceil – B$ ,其中 $0\le A,B \le \left \lceil \sqrt p \right \rceil$ ,则有 $a^{A\left \lceil \sqrt p \right \rceil -B} \equiv b \pmod p$ ,稍加变换,则有 $a^{A\left \lceil \sqrt p \right \rceil} \equiv ba^B \pmod p$ 。

我们已知的是 $a,b$ ,所以我们可以先算出等式右边的 $ba^B$ 的所有取值,枚举 $B$ ,用 hash / map 存下来,然后逐一计算 $a^{A\left \lceil \sqrt p \right \rceil}$ ,枚举 $A$ ,寻找是否有与之相等的 $ba^B$ ,从而我们可以得到所有的 $x$ , $x=A \left \lceil \sqrt p \right \rceil – B$ 。

注意到 $A,B$ 均小于 $\left \lceil \sqrt p \right \rceil$ ,所以时间复杂度为 $\Theta\left (\sqrt p\right )$ ,用 map 则多一个 $\log$ 。

由于可能不存在逆元,所以需要保证$A \lceil \sqrt p \rceil >= B$,所以我们可以让A从1开始,即使这样,x的范围还是可以实现0~p-1。最后代入验证是否满足即可判断是否有解。(两边都是非负次幂,不需要逆元、互质)

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,,

洛谷P4195【模板】扩展BSGS:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter