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…