ZOJ 3254 Secret Code

题意

求小于等于M的数中有多少个可以使得A^x=B(mod C)成立。

思路

首先利用extended BSGS求出最小的x使得A^x=B(mod C)成立。

接下来我们要求出最小的len使得A^(x+len*k)=B(mod C),我们知道模C的指数循环节是Phi(C),对于某个特定的幂的最小循环节则一定是Phi(C)的约数。我们要枚举Phi(C)的各个素因数,不断试除试算,知道得到最小的循环节长度len。

得到了x和len之后,答案就是(M-x)/len+1。

代码

 

SPOJ MOD Power Modulo Inverted

题意

求最小的x使得A^x=B(mod C)。

思路

HDU 2815 Mod TreePOJ 3243 Clever Y完全一致,extended BSGS的模板题。

代码

 

HDU 2815 Mod Tree

题意

题目翻译好之后实际上是求解最小的x使得A^x=B(mod C)成立,C不保证是素数。

思路

典型的Extended BSGS模板题。

需要注意的是,内存空间比较紧张,HASH空间不宜开得太大,需要牺牲一些时间换空间。

代码

 

POJ 3243 Clever Y

题意

求解最小的x使得A^x=B(mod C)成立,C不保证是素数。

思路

C不保证素数的BSGS,这时使用扩展BSGS解决,扩展BSGS的实质是在BSGS之前利用这个定理:

Ad=Bd(mod C) <=> A=B(mod C/gcd(C,d))

将问题转化为一般BSGS能够解决的形式,再使用一般BSGS解决。

代码

POJ 2417 Discrete Logging这个问题中也使用了如下exBSGS的代码。

 

POJ 2417 Discrete Logging

题意

求解最小的x使得A^x=B(mod C)成立。数据保证了C一定为素数。

思路

解决这种问题是有一种特定算法Baby Step Giant Step的。BSGS算法的具体思想这里不再赘述。直接套用就可以了。

代码

 

 

Scroll to top