题意
：
题解
：
BSGS
代码
：
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long
#define int long long
const ll N=1e8+5;
ll ksm(ll a, ll p, ll mod) {
ll res=1;
while(p) {
if(p&1) res=res*a%mod;
a=a*a%mod;
p>>=1;
}
return res;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x=1;
y=0;
return a;
}
ll ans=exgcd(b, a%b, y, x);
y=y-a/b*x;
return ans;
}
ll inv(ll a, ll mod) {//存在逆元条件：gcd(a,mod)=1
ll x, y;
ll g=exgcd(a, mod, x, y);
if(g!=1) return -1;
return (x%mod+mod)%mod;
}
ll bsgs(ll a,ll b,ll p)
{
b%=p;
if(b==1||p==1)return 0;
ll n=sqrt(p);
static unordered_map<ll,ll>Bmp;
Bmp.clear();
ll inva=inv(ksm(a,n-1,p),p)*b%p;
for(ll i=n-1;i>=0;i--)
{
Bmp[inva]=i;inva=inva*a%p;
}
ll ta=1,powa=ksm(a,n,p);
for(ll k=0;k<=p;k+=n)
{
if(Bmp.count(ta))return k+Bmp[ta];
ta=ta*powa%p;
}
return -1;
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int a, b, M, x0, x;
cin>>a>>b>>M>>x0>>x;
bool q=0;
if(x==x0) q=1;
else if(a==0) {
if(b==x) q=1;
else q=0;
}else if(a==1) {
if(b) q=1;
else q=0;
}else {
int aa=ksm(a-1,M-2,M)%M;
int t=((x+b*aa)%M*ksm(x0+b%M*aa%M,M-2,M)%M)%M;
if(bsgs(a,t,M)==-1) q=0;
else q=1;
}
if(q) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
总结
Qaq
