看别人做的很简单我也不知道是怎么写出来的
自己拿到这道题的想法就是模为素数，那必然有原根r ，将a看做r^a , b看做r^b
那么只要求出幂a，b就能得到所求值a,b
自己慢慢化简就会发现可以抵消n
然后扩展欧几里得解决，一个个枚举所有模的情况。。。。
中间利用了欧拉准则可以知道 对所有奇素数而言： a^((p-1)/2) = -1(mod p)
利用上述准则，这样就不用baby_step giant_step的办法了
#include <bits/stdc++.h>
using namespace std;
typedef long long LL; const int N = ; LL P , k1,b1 , k2;
bitset<N> prime;
int p[N],pri[N];
int k,cnt; void isprime()
{
prime.set();
for(int i=; i<N; i++)
{
if(prime[i])
{
p[k++] = i;
for(int j=i+i; j<N; j+=i)
prime[j] = false;
}
}
} void Divide(int n)
{
cnt = ;
int t = (int)sqrt(1.0*n+0.5);
for(int i=; p[i]<=t; i++)
{
if(n%p[i]==)
{
pri[cnt++] = p[i];
while(n%p[i]==) n /= p[i];
}
}
if(n > )
pri[cnt++] = n;
} void gcd(LL a , LL b , LL &d , LL &x , LL &y)
{
if(!b){d=a;x=;y=;}
else{gcd(b,a%b,d,y,x);y-=x*(a/b);}
} LL inv(LL a , LL n)
{
LL d,x,y;
gcd(a,n,d,x,y);
return d==?(x+n)%n:-;
} LL quick_mod(LL a,LL b,LL m)
{
LL ans = ;
a %= m;
while(b)
{
if(b&)
{
ans = ans * a % m;
b--;
}
b >>= ;
a = a * a % m;
}
return ans;
} LL pow_mod(LL a , LL p , LL n)
{
LL ret= ;
while(p){
if(p&) ret = ret*a%n;
a = a*a%n;
p>>=;
}
return ret;
} LL mul_mod(LL a , LL b , int n)
{
return a*b%n;
} //int log_mod(int a , int b , int n)
//{
// int m , v , e=1 , i;
// m = (int)sqrt(n+0.5);
// v = inv(pow_mod(a,m,n) , n);
// map<int,int>x;
// x.clear();
// x[1] = 0;
// for(i=1 ; i<m ; i++){
// e = mul_mod(e , a , n);
// if(!x.count(e)) x[e]=i;
// }
// for(i=0 ; i<m ; i++){
// if(x.count(b)) return i*m+x[b];
// b = mul_mod(b,v,n);
// }
// return -1;
//} #define pii pair<int,int>
pii ans[N]; int main()
{
// freopen("a.in" , "r" , stdin);
int cas = ;
isprime();
//>>k1>>b1>>k2
while(cin>>P>>k1>>b1>>k2)
{
printf("Case #%d:\n" , ++cas);
int tot = ;
/*P==2另外处理*/
if(P==){
printf("%d %d\n" , ,);
continue;
}
if(P==){
printf("%d %d\n" , ,);
continue;
}
Divide(P-); for(int g=; g<P; g++)
{
bool flag = true;
for(int i=; i<cnt; i++)
{
int t = (P - ) / pri[i];
if(quick_mod(g,t,P) == )
{
flag = false;
break;
}
}
if(flag)
{
LL root = g;
LL val = (P-)/;
// cout<<root<<" "<<val<<endl;
LL d,x,y;
gcd(b1+k1 , - , d , x , y);
x = x*val , y = y*val; x = ((x%(P-))+(P-))%(P-);
y = ((y%(P-))+(P-))%(P-);
for(int i= ; i<P- ; i++){ if((x*k1-y*k2)%(P-)==){
LL a = pow_mod(root , x , P);
LL b = pow_mod(root , y , P);
if(a>&&b>) ans[tot++] = make_pair((int)a , (int)b);
}
x = (x+)%(P-);
y = (y+b1+k1)%(P-);
}
break;
}
}
sort(ans , ans+tot);
tot = unique(ans , ans+tot)-ans;
if(tot==) puts("-1");
else{
for(int i= ; i<tot ; i++) printf("%d %d\n" , ans[i].first , ans[i].second);
}
}
return ;
}