【题解】Congruence Equation 数学乱搞 CF919E ——quhengyi11

传送门

题目大意：求满足以下式子的 $1\leq n\leq x$的个数

$$n\cdot a^n=b\; (mod\;p)$$

其中 $a,b,p \leq 10^6,x \leq 10^{12}$

老年选手不会推式子系列.jpg

首先我们根据费马小定理，显然可以对 $n$做带余除法 $n=(p-1)q+r$

然后原式子等价于

$$((p-1)q+r)\cdot a^r=b\; (mod\;p)$$

我们移一下项：

$$q=(b – r\cdot a^r)((p-1)\cdot a^r)^{-1}\; (mod\;p)$$

听说可以再化简（然而我代码里还是按上面那个式子写的

$$q=r-b\cdot a^{-r}\; (mod\;p)$$

然后对于一个 $r$，我们总可以找到一个在膜 $p$意义下唯一的 $q$呢

那么我们再讨论一下对于每一种 $r$有多少个 $q$可以取

首先 $n=(p-1)q’+r$

根据原式我们有 (这里 $q’\geq q$)

$$(p-1)q’+r=(p-1)q+r\;(mod\; p)$$

因为 $(p,p-1)=1$，于是有

$$q’=tp+q\quad \quad t\geq 0$$

我们又有

$$x \geq n = (p-1)q’+r$$

进一步推导

$$\frac{x-r}{p-1} \geq q’$$

也就是

$$\frac{x-r}{p-1}-q \geq tp$$

令 $maxq = \frac{x-r}{p-1}$
然后我们就知道了 $t$的最大值为 $\frac{maxq – q}{p}$

所以 $t$的有 $\frac{maxq – q}{p} + 1$种取法

枚举 $r$统计答案就行啦

还有一个细节是 $n\geq 1$，所以如果 $q$和 $r$都是 $0$的时候要减一

代码

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define Re register
#define pb push_back
#define F first
#define S second
#define ll long long
#define lowbit(x) (x & -x)
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 1000000007
#define N 50005
#define M 100005
ll a, b, p, x, ans, ar;
inline ll pow (ll x, ll y, ll mod)
{
    ll ret = 1;
    while (y)
    {
        if (y & 1) ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
int main ()
{
    scanf("%lld %lld %lld %lld", &a, &b, &p, &x);
    ll up = p - 2;
    fo (r, 0, up)
    {
        ar = pow(a, r, p);
        ll q = (pow(ar * (p - 1) % p, p - 2, p) * (b - ar * r) % p + p) % p;
        ll qmax = (x - r) / (p - 1);
        if (x >= r && qmax >= q)
        {
            ans += (qmax - q) / p + 1;
            if (!q && !r) --ans;
        }
    }
    printf("%lld", ans);
}