C++14(g++5.4) 解法, 执行用时: 59ms, 内存消耗: 8300K, 提交时间: 2020-05-30 18:37:53

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+5;
ll a,b,p,x,ans=0,res[maxn];
int main(void)
{	
    cin>>a>>b>>p>>x;
    res[p-1]=b;
    for(int i=p-2;i>=0;i--){
    	res[i]=res[i+1]*a;
    	res[i]%=p;
	}
    for(int i=0;i<p-1;i++){
    	ll t=res[i]+p*(i-res[i]+2*p-2);
    	t%=p*(p-1);
        ans+=((x-t+(p*(p-1)))/(p*(p-1)));
    }
    cout<<ans<<"\n";
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 36ms, 内存消耗: 404K, 提交时间: 2020-10-08 11:28:27

#include<bits/stdc++.h>
using namespace std;
long long a, b, p, x, t, xx, ans = 0, v = 1, i, m;
int main()
{
	cin >> a >> b >> p >> x;
	ans = 0, v = 1;
	for (i = 1; i <= p - 2; i++) v = v*a%p;
	m = p*(p - 1);
	for (i = 0; i<p - 1; i++)
	{
		t = (i - b) % (p - 1);
		if (t<0) t += p - 1;
		xx = b + p*t;
		ans += x / m;
		if (x%m >= xx) ans++;
		b = b*v%p;
	}
	cout << ans << endl;
}