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
【样例输入3】
3 3
2 1 3
2 2 3
2 3 3
【数据规模和约定】
对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。
Sample Output
【样例输出1】
2
1
2
【样例输出2】
2
1
0
【样例输出3】
0
1
Orz, I cannot find x!
分析：
基础数论
第一类询问
KSM没什么可以说的，
唯一需要注意的就是在乘的时候时刻%，防止乘爆了
第二类询问
xy≡z(mod p)
我们先求解：x’y≡1(mod p),x’和y互为拟元
则x=x’*z
然而x是非负整数，所以如果计算出来是负数，我们要不停地加p
这个拟元的求解，有两种方法
1.扩展欧几里得
x*y≡1 （mod p）
转化成：xy-kp=1，已知y,p，
若gcd(y,p)=1(即y，p互质)
我们就可以用扩欧求解，
反之若gcd(y,p)!=1,我们就可以愉快的输出无解
2.费马小定理
费马小定理的要求是y和p互质
但是题目中没有特殊说明，所以这种方法不考虑
第三类询问
bsgs模板
tip
最近练习dp和数据结构较多
发现一个很可怕的事情，就是数论的理论都懂
但是不会实际操作，很慌
很庆幸现在发现了这个问题，
赶紧在联赛前好好练习ヾ(◍°∇°◍)ﾉﾞ
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<cmath>
#define ll long long
using namespace std;
int T,K;
int x,y,z,p;
ll xx,yy;
map<ll,int> mp;
ll KSM(ll x,int y,ll p)
{
ll t=1;
x%=p;
while (y)
{
if (y&1)
t=(t%p*x%p)%p;
x=(x%p*x%p)%p;
y>>=1;
}
return t%p;
}
int gcd(int a,int b)
{
int r=a%b;
while (r)
{
a=b;b=r;r=a%b;
}
return b;
}
void kuo(int a,int b)
{
if (b==0){
xx=1; yy=0;
return;
}
else
{
kuo(b,a%b);
ll t=yy; //顺序不能反
yy=xx-(a/b)*yy;
xx=t;
}
}
void doit(int y,int z,int p) //y*x≡1 (mod p)
{
int t=gcd(y,p);
if (z%t!=0) { ///
printf("Orz, I cannot find x!
");
return;
}
y/=t; z/=t; p/=t;
kuo(y,p);
xx=(ll)(xx%p*z%p)%p;
while (xx<0) xx+=(ll)p;
printf("%lld
",xx);
}
int bsgs()
{
mp.clear();
y%=p;
z%=p;
if (y==0&&z==0) return 0;
if (y==0) return -1;
ll m=(ll)ceil(sqrt((double)p)),now=1;
mp[1]=m+1;
for (int i=1;i<m;i++)
{
now=(now%p*y%p)%p;
if (!mp[now]) mp[now]=i;
}
ll inv=1,tmp=KSM(y,p-m-1,p);
for (int k=0;k<m;k++)
{
int i=mp[(z%p*inv%p)%p];
if (i)
{
if (i==m+1) i=0;
return (int)(k%p*m%p+i)%p;
}
inv=(inv%p*tmp%p)%p;
}
return -1;
}
int main()
{
scanf("%d%d",&T,&K);
if (K==1)
{
for (int i=1;i<=T;i++)
{
scanf("%d%d%d",&x,&y,&p);
printf("%lld
",KSM((ll)x,y,(ll)p));
}
}
else if (K==2)
{
for (int i=1;i<=T;i++)
{
scanf("%d%d%d",&x,&y,&p);
doit(x,y,p);
}
}
else
{
for (int i=1;i<=T;i++)
{
scanf("%lld%lld%lld",&y,&z,&p);
int o=bsgs();
if (o!=-1) printf("%d
",o);
else printf("Orz, I cannot find x!
");
}
}
return 0;
}