题目
解题思路
分三个部分，考验算法了。
1.
第一个操作很简单，就是一个快速幂，这里有人可能会问可不可以用降幂公式。所谓降幂公式，其实就这样。
我们看一下数据范围，发现m确实可能是非常大的，又是一个质数，因而的值就是m-1,细细看一下，发现可能得不偿失，还不如不用得了。因而直接用快速幂。
2.
第二个操作就是解一个二元一次不定方程，我们姑且用表示一下。算法用exgcd即可，以前有一道题目好像用exgcd就直接得到最小正整数解，这里我觉得是数据的问题，因而我们还应进行处理，按照叶学长的说法，用一些简单的四则运算就可以得到我们想要的特解。
在这里先表示通解。
这里的u为b/d，v即为-a/d,d=(a,b)。
方程无解的情况其实比较好判断，仅需判断c是否整除d即可。
3.
最近新学的一个算法BSGS，刚开始感觉难度很大，也不好打代码，现在倒是慢慢理解了。
这个算法求解
条件要使得a,p互质，这里有问题了，数据只说p为素数却未说互质，因此我们要单独判断一下，如果a % p等于0了，当b等于1时有一个解0，否则无解。
我们令
可以保证
于是
我们将k*m保留在左边，于是我们就可以处理出b * a的i（i<=r）的值保存在map中。因而再枚举左边，发现map中有即可。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
int n,k,y,z,p;
map<long long,long long>mp;
void exgcd(int a,int b,int &gcd,long long &x,long long &y){
if (b == 0){
gcd = a;
x = 1,y = 0;
return ;
}
exgcd(b,a % b,gcd,y,x);
y -= (a / b) * x;
return ;
}
long long qkpow(long long x,long long y,long long mod){
long long ans = 1;
while (y){
if (y & 1)
ans = ans * x % mod;
x = x * x % mod;
y /= 2;
}
return ans;
}
void solve1(int y,int z,int p){
printf("%lld
",qkpow(y,z,p));
}
void solve2(int y,int z,int p){
int gcd = 0;
long long x0,y0;
exgcd(y,p,gcd,x0,y0);
if (z % gcd != 0){
printf("Orz, I cannot find x!
");
return ;
}
x0 = z / gcd * x0;
long long t = abs(x0) / (p / gcd);
if (x0 < 0){
x0 += (p / gcd) * t;
while (x0 < 0)
x0 += (p / gcd);
}
else if (x0 > 0)
{
x0 -= (p / gcd) * t;
while (x0 < 0)
x0 += (p / gcd);
}
printf("%lld
",x0);
}
void solve3(int y,int z,int p){
if (y % p == 0){
if (z == 1){
printf("0
");
return ;
}
else {
printf("Orz, I cannot find x!
");
return ;
}
}
long long m = ceil(sqrt(p));
long long sum = 1;
for (int i = 0;i <= m;i ++){
mp[sum * z % p] = i;
sum = sum * y % p;
}
long long s = qkpow(y,m,p);
long long tmp = 1,ans = -1;
for (int i = 1;i <= m;i ++){
tmp = tmp * s % p;
if (mp[tmp]){
ans = m * i - mp[tmp];
break;
}
}
if (ans == -1)
printf("Orz, I cannot find x!
");
else
printf("%lld
",ans);
mp.clear();
}
int main(){
while (scanf ("%d%d",&n,&k) != EOF){
for (int i = 1;i <= n;i ++){
scanf("%d%d%d",&y,&z,&p);
if (k == 1)
solve1(y,z,p);
if (k == 2)
solve2(y,z,p);
if (k == 3)
solve3(y,z,p);
}
}
}