題意:有三種要求:
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)的最小非負整數。
分別處理即可
思路:
1顯然是快速冪了,純模板
2是擴展歐幾裡得(exgcd),求滿足xy-pk=z的最小x(k任意)
3利用了費馬小定理的性質a^(p-1)≡1(mod p),然後分塊降復雜度(太麻煩懶得寫直接抄黃學長代碼…捂臉)
/**************************************************************
Problem: 2242
User: Rainbow6174
Language: C++
Result: Accepted
Time:2028 ms
Memory:3272 kb
****************************************************************/
#include
#include
#include
#include