数论的板子集合……
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”之间有一个空格。
题目分析
第一个问题：快速幂解决
第二个问题：1.转为exgcd问题 2.直接$x=Z*y^{-1}$
第三个问题：BSGS
BSGS是引入分块的思想解决形如$A^x≡B(mod\,C) C为素数$的问题（至于C不是素数就是exBSGS的范畴了）
具体来说，就是记$size=\sqrt C$，$x=i*size-j \, (0≤j<\sqrt C)$，于是式子就成了$A^{i*size}≡A^j*B$的形式。而右边这个东西是可以预处理出来放在hash表里的，这样在$\sqrt C$枚举$i$的过程中，就可以$O(1)/O(log \, n)$判断是否有相应的j了。
这类思想挺妙的，应该可以迁移到其他地方。
#include<bits/stdc++.h>
typedef long long ll; int T,k;
ll x,y,p,w,z,d,cir;
std::map<ll, int> mp; ll qmi(ll a, ll b)
{
ll ret = ;
for (a%=p; b; b>>=, a=a*a%p)
if (b&) ret = ret*a%p;
return ret;
}
ll gcd(ll a, ll b){return !b?a:gcd(b, a%b);}
void exgcd(ll a, ll b, ll &x, ll &y)
{
if (!b){
x = , y = ;
return;
}
exgcd(b, a%b, y, x), y -= a/b*x;
}
ll BSGS(ll a, ll b, ll p)
{
if (((!b)&&(!a))) return ;
if ((!a)&&b) return -;
if (b==) return ;
ll size = ceil(sqrt(p)), bse = ;
mp.clear();
for (int i=; i<size; i++)
{
mp[bse*b%p] = i;
bse = bse*a%p;
}
for (ll i=, now=; i<=p; i+=size, now = now*bse%p)
if (mp.count(now)) return ((i-mp[now])%p+p)%p;
return -;
}
int main()
{
for (scanf("%d%d",&T,&k); T; --T)
{
scanf("%lld%lld%lld",&x,&y,&p);
if (k==) printf("%lld\n",qmi(x, y));
if (k==){
x %= p, y %= p;
if (!x) puts("Orz, I cannot find x!");
else printf("%lld\n",y*qmi(x, p-)%p);
}
if (k==){
x %= p, y %= p, d = BSGS(x, y, p);
if (d==-) puts("Orz, I cannot find x!");
else printf("%lld\n",d);
}
}
return ;
}
END