【Bzoj2242】计算器

2242: [SDOI2011]计算器

Time Limit: 10 Sec Memory Limit: 512 MB Submit: 3419 Solved: 1341 [Submit][Status][Discuss] Description

你被要求设计一个计算器完成以下三项任务： 1、给定y,z,p,计算Y^Z Mod P 的值； 2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数； 3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。 Input

输入包含多组数据。 第一行包含两个正整数T,K分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。 以下行每行包含三个正整数y,z,p，描述一个询问。 Output

对于每个询问，输出一行答案。对于询问类型2和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”，注意逗号与“I”之间有一个空格。 Sample Input

【样例输入1】 3 1 2 1 3 2 2 3 2 3 3 【样例输入2】 3 2 2 1 3 2 2 3 2 3 3 【数据规模和约定】 对于100%的数据，1<=y,z,p<=10^9，p为质数，1<=T<=10。 Sample Output

【样例输出1】 2 1 2 【样例输出2】 2 1 0

数学の特定のテ-マは本当に恐ろしいquq… 这个题的话能算是一个综合题吧，三个操作对应着不同的算法。 对于第一个操作，比较简单，快速幂。 对于第二个操作，可以选择用扩展欧几里得解这个同余方程。但是我们注意到p为质数，可以使用费马小定理求解。首先考虑有没有解，如果y%p==0而z%p!=0的话，很显然Orz（这时无论x等于多少左边余数都为0）。之后我们用费马小定理求解，∵xy≡z(modp)$∵xy≡z (mod p)$，∴x≡z∗inv(y)(modp)$∴x≡z*inv(y) (mod p)$。而又因为p是质数且y$y%p!=0$，所以y，p肯定互质，此时由费马小定理得：inv(y)$inv(y)$ = yp−2${y^{p-2}}$。之后再以p为步长将x调整至最小非负整数。 而对于第三个操作，我就不讲了因为我也不会 我们可以用BSGS/离散对数算法（我会告诉你我一个也不会？）。稍微介绍一下BSGS算法的思路。 网上的许多题解中，是将x$x$拆分为i∗m+j$i*m+j$，之后求逆元然后hash出解。像这样： （摘自hzwer）

但是这道题可以使用另一种方法稍作简化，可以省去求逆元的步骤（你tm不会玩逆元就直说！！！）。 我们可以设x=im−j$x=im-j$，注意这个美妙的减号，移项之后就没有逆元了，这样原式就变为yi∗m−j$y^{i*m-j}$=z(modp)，$z (mod p)，$ 再变为yj×z$y^{j}×z$=ym∗i$y^{m*i}$ (modp)$(mod p)$。 这时候我们就可以按照上文中的思路，枚举j：0 to m，把左边式子模p的值存入map中，之后再枚举i：1 to m，如果发现一个ym∗i$y^{m*i}$模p的值在map中有对应解，则ans = (i*m)-ma[tmp]（tmp是左边式子已经有的值），然后对ans进行调整即可。 那么肯定有人会有疑问为何只计算到m=p√$/sqrt p$就可以确定答案呢？ x=i∗m−j$x=i*m-j$ 也就是x的最大值不会超过p,那超过p的怎么办 ？ 有一个公式 akmodp$a^{k mod p}$=ak(modp)$a^k (mod p)$ 这个公式的推导需要用到费马小定理 k mod p可以看做 k-mp ,原式可化成 ak(ap)m=ak(modp)$/frac{a^k}{(a^p)^m}=a^k (mod p)$ 根据费马小定理 ap$a^p$=1 (mod p) 其中p为质数 ，a,p 互质，可得ak1m=ak(modp)$/frac{a^k}{1^m}=a^k (mod p)$ 即 ak=ak(modp)$a^k=a^k (mod p)$ 得证。

唔…这个奇妙的方法我是真的没懂，有没有神犇愿意给我讲一讲quq…