CF919E Congruence Equation

模拟和逆元题目。

1. 题意

求

$$n\cdot a^n\equiv b\pmod p$$

在 $[1,x]$ 的正整数解的个数，其中 $a,b,p,x$ 给定。

$p\leq10^6+3,x\leq10^{12},1\leq a,b<p$。

2. 思路

首先，看到 $p\leq10^6+3$，一定是要 $O(p)$ 枚举，然后再做。

a）枚举 $n$

那么，原题转化为了 $t\cdot a^n\equiv b\pmod p$ 的解了。

很明显是一个 BSGS，时间复杂度为 $O(\sqrt p)$ 或 $O(\sqrt p\log \sqrt p)$，取决于 map 还是 Hash。

但是，总时间为 $O(p\sqrt p)$，很明显无法通过。

b）枚举 $a^n$

首先，我们考虑 $a^n$ 的取值有多少种。

由于 $a^{p-1}\equiv 1\pmod p$，所以循环节一定是 $p-1$，那么我们就可以枚举 $n\bmod (p-1)$，得到所有的 $a^n$ 的取值。

那么，原题就是 $n\cdot t\equiv b\pmod p$ 的解。

咦，这不就是一个逆元了吗？

于是，我们可以 $O(\log p)$ 求出逆元（因为一定有），那么，我们就可以求出 $n\bmod p$ 的值。

c）合并答案

这道题在 CF 上有中国剩余定理的标签，大概就是这里用的吧。

我们已经得到了 $t1=n\bmod (p-1)$ 和 $t2=n\bmod p$ 的值，直接由中国剩余定理就可以了。

其实手玩也不是不可以，直接设 $n=kp+t2$，代入第一个就可以得到：

$$\begin{aligned} kp+t2&\equiv t1 \pmod {p-1}\\ k+t2&\equiv t1\pmod {p-1}\\ k&\equiv t2-t1\pmod {p-1} \end{aligned}$$

就解出了 $n$ 的最小正整数取值了。

周期很明显是 $p\cdot(p-1)$，将答案加入即可。

3. 代码

实际实现的时候可以预处理算出 $a$ 的逆元，每次枚举 ${a^t}$ 的逆元的时候可以通过 ${a^{t-1}}^{-1}$ 乘上 $a^{-1}$ 即可。

码风略丑，请见谅。

int main()
{
	cin >> a >> b >> Mod >> x;
	ll now = b, inv = qpow(a, Mod - 2), lim = Mod * (Mod - 1), ans = 0;
	for (ll modp1 = 0; modp1 < Mod - 1; ++ modp1, now = now * inv % Mod)
	{//modp1 是枚举的 t，now 就是上面的 b 乘以（ a 的 t 次方的逆元），也就是 t1
		ll mx = (modp1 - now + (Mod - 1)) % (Mod - 1) * Mod + now;//mx 是 n 的最小取值
		mx = (mx % lim + lim) % lim;//lim 是 Mod * Mod - 1，是 n 的周期
		if (mx <= x) ans += (x - mx + lim) / lim;
	}
	cout << ans << endl;
	return 0;
}