标签为 [BSGS] 的文章

BZOJ2242 计算器

题目大意 你被要求设计一个计算器完成以下三项任务: 给定y,z,p,计算Y^Z Mod P 的值; 给定y,z,p,计算满足xy≡ z ( mod P )的最小非负整数; 给定y,z,p,计算满足y^x ≡ z ( mod P)的最小非负整数。 对于100%的数据,1<=y,z,p<=10^9,为质数,1<=T<=10。 Solution 典型的NOIP三合一题,硬是把三道题合在了一起…… 前两问就不说了(一个快速幂,一个exgcd)…… 而要怎么解决第三问呢? 要用到BSGS(Baby-Step-Giant-Step)算法。用某方姓大佬的话: 就是枚举到根号的暴力 设x=im-j $ y^x=y^{im-j}\equiv z(mod p)$即$ y^{i ......