本文共 729 字，大约阅读时间需要 2 分钟。

给出a, b, p, x，求有多少个n满足①n*a^n%p==b；②n<=x

思路：先要知道一个很简单的性质：a^n%p的值一定存在循环节（n=0就进入循环），且周期T一定是p-1的约数

然后就好做了，①暴力枚举a^i%p（i从0到p-1）算出每个余数ki，可以得到式子c*ki%p==b

②对于每个ki，用逆元求出c，c = b*(ki对p的逆元)

③如果存在一个n满足n*a^n%p==b，那么很显然n%(p-1)==i 并且n%p==c，最小的n可以用求出

④然后就是一个简单的除法了，对于所有<=x的n的倍数都满足条件

复杂度O(plogp)

#include
   
    #define LL long longLL k[1005555];LL Pow(LL a, LL b, LL p){	LL ans = 1;	while(b)	{		if(b%2)			ans = ans*a%p;		a = a*a%p;		b /= 2;	}	return ans;}int main(void){	LL a, b, p, x, i, xh, last, c, n, ans;	scanf("%lld%lld%lld%lld", &a, &b, &p, &x);	ans = 0, xh = p-1;	for(i=0;i<=p-2;i++)	{		k[i] = Pow(a, i, p);		c = Pow(k[i], p-2, p)*b%p;		n = ((p-1)*(p-1)*c+p*i)%(p*(p-1));		ans += (x-n+p*(p-1))/(p*(p-1));	}	printf("%lld\n", ans);	return 0;}