【BZOJ2242】【SDOI2011】计算器

终于学BSGS啦!

前两问送分

第三问是一个叫做离散对数的东西

要求\(y^x\equiv z\pmod p\)的最小非负整数解

我们首先令\(s=\sqrt p\)

那么一个\(x\)可以被唯一表示为\(x=ks+b\),其中\(b<s\)

那么我们先将所有的\(y^b\)算出并存起来

然后枚举\(k\),用第二问的方法计算出\(zy^{-ks}\),查找一下这个数是否出现,出现说明找到了

说点什么

  Subscribe  
提醒