Description

题面

\(n*a^n≡b (\mod P),1<=n<=x\)

Solution

令 \(n=(P-1)*i+j\)

\([(P-1)*i+j]*a^{[(P-1)*i+j]} ≡b (\mod P)\)

由费马小定理

\([(P-1)*i+j]*a^j ≡b (\mod P)\)

\(i ≡j-\frac{b}{a^{j}} (\mod P)\)

然后就可以枚举\(j\)，算\(i\)的取值种数了

利用 \(i\) 的限制：\(i*(P-1)+j<=x\)，可以算出取值范围是一个前缀，再在前缀中算出满足同余要求的即可

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a,b,P,x;

ll qm(ll x,ll k){

  ll sum=1;

  while(k){

    if(k&1)sum=1ll*sum*x%P;

    x=x*x%P;k>>=1;

  }

  return sum;

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  cin>>a>>b>>P>>x;

  ll inv=qm(a,P-2),aj=b,ans=0;

  for(int j=0;j<P-1;j++){

    ll i=(j-aj)%P;

    if(i<0)i+=P;

    if(x>=j && (x-j)/(P-1)>=i){

      ll t=(x-j)/(P-1);

      ans+=t/P+(t%P>=i);

    }

    aj=aj*inv%P;

  }

  if(b==0)ans--;

  cout<<ans<<endl;

  return 0;

}