第十五届吉林省赛The 15th Jilin Provincial Collegiate Programming Contest C.Random Number Generator（数学 BSGS)

题目链接

题意

：

题解

：
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)=1ll 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