首页 > 代码库 > [原博客] BZOJ 2242 [SDOI2011] 计算器
[原博客] BZOJ 2242 [SDOI2011] 计算器
题目链接
noip级数论模版题了吧。
让求三个东西:
- 给定y,z,p,计算Y^Z Mod P 的值。
- 给定y,z,p,计算满足xy≡ Z ( mod P )的最小非负整数。
- 给定y,z,p,计算满足Y^x ≡ Z ( mod P)的最小非负整数。
其中P均为素数。
来分着处理。
1 y^z%p
快速幂。
推荐一种又快又好写的写法。
1 LL power_mod(LL a,LL b,LL p){ //get a^b%p2 LL ret=1;3 while(b){4 if(b&1) ret = ret * a % p;5 a = a * a % p;6 b>>=1;7 }8 return ret;9 }
为什么是对的呢,拆成二进制看一看就好了。
2 Yx==Z%p
扩展欧几里德。
Yx==Z%p
可以变形成为Yx+py==Z
显然仅当gcd(Y,p)|Z
时有解。
我们知道ex_gcd可以求 ax0+by0==gcd(a,b)
的一组解。
所以我们让原方程两边都除以gcd(Y,p)
,然后得到Yx0+py0==gcd(Y,p)
的一组解。
于是Z/gcd(Y,p)*x0%p
为原题的答案。注意要让结果为正。
3 Y^x %p ≡ Z
Baby step-giant step
其实也是一种分块的思想。
设 m=√p
。
可以表示为 Y^(km) * Y^r == Z (mod P)
。
注意到0<=r<m
只有√p
种取值,所以我们可以预处理出来,算出它的逆元再乘Z,扔进一个set。
然后枚举k,set中查询Y^(km),如果有这个值,就说明找到了解。
逆元的话。因为p是素数,所以直接power_mod(Y,p-2,p);
就好了。
从原博客搬运过来。
[原博客] BZOJ 2242 [SDOI2011] 计算器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。