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

题目

题目描述
求这个关于 $n$ 的同余方程的不超过 $x$ 的正整数解：$$n\cdot a^n\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

数据范围与提示
$2\le p\le 10^6+3$ 且 $1\le a,b<p$ 且 $1\le x\le 10^{12}$ 。

思路

利用类似大步小步的方法。

设 $$n=qm-r(0\le r<m)$$

代入原式得到 $$(qm-r)a^{qm-r}\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

即$$(qm-r)a^{qm}\equiv b\cdot a^r(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

似乎项数太多，做不了？不妨规定 $m|p$ ，重新审视式子，得到 $$-r\cdot a^{qm}\equiv b\cdot a^r(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

于是可以拿到经典的大步小步式子 $$a^{qm}\equiv -r^{-1}{a}^r\cdot b(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

为了满足 $\mathcal{O}(m)=\mathcal{O}(\sqrt{x})$ 且 $m|p$ ，可以令 $m=p\lfloor \frac{\sqrt{x}}{p}\rfloor$ ，时间复杂度就是 $\mathcal{O}(\sqrt{x})$ 的。

代码

极致的压行，给你极致的阅读体验。

#include <cstdio>#include <iostream>#include <vector>#include <algorithm>#include <cstring>using namespace std;inline long long readint(){   	long long a = 0; char c = getchar(), f = 1;	for(; c<'0' or c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c and c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}inline void writeint(long long x){   	if(x > 9) writeint(x/10);	putchar((x%10)^48);}# define MB template < class T >MB void getMax(T &a,const T &b){    if(a < b) a = b; }MB void getMin(T &a,const T &b){    if(b < a) a = b; }const int MaxP = 1000005;int cnt[MaxP], inv[MaxP]={   1,1};int main(){   	int a = readint(), b = readint(), p = readint();	int rp = p; /* real p */ p = p*(MaxP/p);	long long x = readint(); // 会爆int	if(x%p == 0) -- x; // 下面就可以省去取模	for(int i=(inv[1]=1)+1; i<rp; ++i)		inv[i] = (0ll+rp-rp/i)*inv[rp%i]%rp;	int a_p = 1; /* a的p次方 */ long long ans = 0;	for(int i=1; i<=p; ++i) a_p = 1ll*a_p*a%rp;	/* 第一次计算 */	for(int r=1,now=rp-b; r<p; ++r) now = 1ll*now*a%rp,		((r%rp != 0) && ++ cnt[1ll*now*inv[r%rp]%rp]);	for(int m=1,now=1; 1ll*m*p-(p-1)<=x; ++m)		now = 1ll*now*a_p%rp, ans += cnt[now];	/* 去掉不合法 */	for(int i=0; i<MaxP; ++i) cnt[i] = 0; // 清空	for(int r=1,now=rp-b; r<p-(x%p); ++r) now = 1ll*now*a%rp,		((r%rp != 0) && ++ cnt[1ll*now*inv[r%rp]%rp]);	for(int m=1,now=1; true; ++m)		if(1ll*m*p-(p-1) > x){   			ans -= cnt[now]; break;		} else now = 1ll*now*a_p%rp;	printf("%lld\n",ans);	return 0;}