Description

题库链接

求满足 \[n\cdot a^n\equiv b \pmod{p}\] 的 \(n\) 的个数， \(1\leq n\leq x\) ， \(a,b,p,x\) 均已给出。

\(2\leq p\leq 10^6+3,1\leq a,b < p, 1\leq x\leq 10^{12}\) ， 保证 \(p\) 是质数。

Solution

对于 \(x\leq 10^{12}\) 显然不能枚举判断。但我们注意到当关于 \(n_1,n_2\) 的方程，若满足 \(n_1\equiv n_2\pmod{p(p-1)}\) 那么这两个方程就是等价的。

理由可以由费马小定理 \(a^{p-1}\equiv1\pmod{p}\) ，以及 \(x\equiv x-p\pmod{p}\) 得到。

我们假设 \(n=i(p-1)+j\) ，那么 \[\begin{aligned}n\cdot a^n&\equiv b &\pmod{p}\\ i(p-1)+j&\equiv b\cdot a^{-j}&\pmod{p}\\ j-i&\equiv b\cdot a^{-j}&\pmod{p}\end{aligned}\]

由于 \(j\) 可能的取值只有 \(p-1\) 个，我们可以枚举 \(j\) 来算出对应的 \(i\) 的个数，也就是 \(n\) 的个数。值得注意的是由于 \(n\) 不能取 \(0\) 所以为了方便处理，让 \(j=0\) 变为 \(j=p-1\) 。

枚举 \(j\) 后我们可以求出最小的 \(i\) ： \(i\equiv j-b\cdot a^{-j}\pmod{p}\) ，进而求出最小的 \(n\) 。然后求出 \([1,x]\) 的范围内的等价的解的个数。

Code

//It is made by Awson on 2018.2.1

#include <bits/stdc++.h>

#define LL long long

#define dob complex<double>

#define lowbit(x) ((x)&(-(x)))

#define Abs(a) ((a) < 0 ? (-(a)) : (a))

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define writeln(x) (write(x), putchar('\n'))

#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

using namespace std;

void read(LL &x) {

    char ch; bool flag = 0;

    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());

    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());

    x *= 1-2*flag;

}

void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }

void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }

LL a, b, p, x;

LL quick_pow(LL a, LL b, LL p) {

    LL ans = 1;

    while (b) {

        if (b&1) ans = ans*a%p;

        a = a*a%p, b >>= 1;

    }

    return ans;

}

void work() {

    read(a), read(b), read(p), read(x);

    LL inva = quick_pow(a, p-2, p);

    LL ans = 0, now = b;

    for (int i = 1; i < p; i++) {

        now = now*inva%p;

        LL n = (p-1)*((i-now+p)%p)+i;

        if (n > x) continue;

        ans += (x-n)/((LL)p*(p-1))+1;

    }

    writeln(ans);

}

int main() {

    work();

    return 0;

}