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。

代码

 

Leave a Reply

Scroll to top