题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2242
第一道BSGS！
咳咳，我到底改了些什么？……
感觉和自己的第一版写的差不多……可能是long long还有%C的位置的缘故？
不过挺欣赏这个板子的。把它记下来好了。
其讲解：https://blog.****.net/clove_unique/article/details/50740412
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#define ll long long
using namespace std;
ll T,type,A,B,C,x,y;
map<ll,ll> mp;
ll pw(ll x,ll k,ll mod)
{
ll ret=;while(k){if(k&)ret=ret*x%mod;x=x*x%mod;k>>=;}return ret;
}
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 gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll solve3()
{
A%=C;B%=C;
if(!A)
{
if(!B)return ;else return -;
}
mp.clear();ll m=ceil(sqrt(C)),t;
for(ll i=;i<=m;i++)
{
if(!i){t=B%C;mp[t]=i;continue;}
t=t*A%C;mp[t]=i;// if cover the previous one,it's correct
}
t=pw(A,m,C);ll ans=t;
for(ll i=;i<=m;i++)
{
if(mp[ans])return (i*m%C-mp[ans]%C+C)%C;//%C的位置
ans=ans*t%C;
}
return -;
}
int main()
{
scanf("%lld%lld",&T,&type);
while(T--)
{
scanf("%lld%lld%lld",&A,&B,&C);
if(type==)
{
B%=(C-);
printf("%lld\n",pw(A,B,C));
}
if(type==)
{
ll g=gcd(A,C);//ll g
if(B%g){printf("Orz, I cannot find x!\n");continue;}
A/=g;C/=g;B/=g;
exgcd(A,C,x,y);
printf("%lld\n",(x*B%C+C)%C);//多%一个C
}
if(type==)
{
ll ans=solve3();
if(ans==-)printf("Orz, I cannot find x!\n");
else printf("%lld\n",ans);
}
}
return ;
}