题目描述

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，为质数，1<=T<=10。

Sample Output

【样例输出1】

2
1
2

【样例输出2】

2
1
0

题目分析

第一问快速幂 第二问exgcd 第三问BSGS
BSGS (拔山盖世) 主要使用了的思想 讲解：传送门

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int t,k;
void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
    if(!b) { x=1,y=0,d=a; return; }
    exgcd(b,a%b,d,x,y);
    long long x0=x;
    x=y,y=x0-(a/b)*y;
}
long long y,z,mod;
long long ksm(long long x,long long y)
{
    long long sum=1;
    while(y)
    {
        if(y&1) sum=(sum*x)%mod;
        y>>=1;
        x=(x*x)%mod;
    }
    return sum;
}
void work1()
{
    scanf("%lld%lld%lld",&y,&z,&mod);
    printf("%lld\n",ksm(y%mod,z));
}
void work2()
{
    scanf("%lld%lld%lld",&y,&z,&mod);
    long long dx,dy,gcd;
    exgcd(y,mod,gcd,dx,dy);
    if(z%gcd!=0)
    {
        printf("Orz, I cannot find x!\n");
        return;
    }
    dx=dx*(z/gcd)%mod;
    dx=(dx%(mod/gcd)+mod/gcd)%(mod/gcd);
    printf("%lld\n",dx);
}
map<long long ,long long> hsh;
long long BSGS(long long a,long long b,long long mod)
{
    if(a%mod==0) return -1;
    hsh.clear();
    long long m=ceil(sqrt(mod));
    long long a_m=ksm(a,m);
    long long mul=b;
    for(long long j=0;j<=m;++j)
    {
        hsh[mul]=j+1;
        mul=mul*a%mod;
    }
    mul=1;
    for(long long i=1;i<=m;++i)
    {
        mul=mul*a_m%mod;
        if (hsh[mul]) return i*m-(hsh[mul]-1);
    }
    return -1;
}
void work3()
{
    scanf("%lld%lld%lld",&y,&z,&mod);
    long long ans=BSGS(y,z,mod);
    if(ans==-1) printf("Orz, I cannot find x!\n");
    else printf("%lld\n",ans); 
}
int main()
{
    scanf("%d%d",&t,&k);
    while(t--)
    {
        if(k==1) work1();
        if(k==2) work2();
        if(k==3) work3();
    }
    return 0;
}