思路：

费马小定理。

n*a^n = b (mod p)

根据费马小定理 a^(p-1) = 1 (mod p)

我们把n化为 n=i+y(p-1)

于是[i+y(p-1)]*a^ [i+y(p-1)] = b (mod p)

再根据费马小定理a^ [i+y(p-1)]=a^i  (mod p)

于是[i+y(p-1)]*a^i = b (mod p)

于是y = (b/(a^i)-i)/(p-1) (mod p)

于是y = (b/(a^i)-i)/(p-1) +k*p(除法用逆元做)

我们发现如果i>p，那么mod p 后还是在0 到 p-1的范围内，所以 0<=i<p，又因为i=0不满足题意，于是0<i<p

于是题目就转换成了遍历i，对于每个i，找有多少个y满足题意

因为n<=x，所以i+y*(p-1)<=x，所以y<=(x-i)/(p-1)，所以对于每个i的y的上界可以确定，找y的个数就很简单了

代码：

#include
     
      using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e6+5;int inv[N];void init(int p){    inv[1]=1;    for(int i=2;i
      
       >=1;        a=(a*a)%p;    }    return ans;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    ll a,b,p,x;    cin>>a>>b>>p>>x;    init(p);    ll ans=0;    for(int i=1;i
       
        x)continue;        ll add=(yy-y)/p+1;        ans+=add;        //cout<
        <<' '<
         
          <<' '<
          
           <<' '<
           
            <