自动搬运

查看原文

来自洛谷，原作者为

	ChenZ01 **

搬运于2025-08-24 21:47:33，当前版本为作者最后更新于2018-12-05 22:28:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

个人博客

欢迎大佬互换友链

Link

洛谷 3306

Solution

大力推式子

$$X_{i + 1} \equiv aX_i + b(\mathrm{mod}\,p)$$ $$X_{i + 1} + \frac{b}{a} \equiv aX_i + b + \frac{b}{a}(\mathrm{mod}\,p) $$$$aX_{i + 1} + b \equiv a^2X_i + ab + b(\mathrm{mod}\,p) $$$$X_{i + 2} \equiv a^2X_i + ab + b(\mathrm{mod}\,p)$$

那么我们得到

$$X_2 \equiv aX_1 + b(\mathrm{mod}\,p)$$ $$X_3 \equiv a ^ 2X_1 + ab + b(\mathrm{mod}\,p)$$ $$X_4 \equiv a ^ 3X_1 + a ^ 2b + ab + b(\mathrm{mod}\,p) $$$$\dots$$ $$X_i \equiv a ^ {i - 1}X_1 + b\sum_{j = 0} ^ {i - 2}a ^ j(\mathrm{mod}\,p) $$

也就是我们要判断如下方程是否有整数解，若有则求解

$$t \equiv a ^ {i - 1}X_1 + b\sum_{j = 0} ^ {i - 2}a ^ j(\mathrm{mod}\,p) $$

继续化化化

$$t \equiv a ^ {i - 1}X_1 + b\sum_{j = 0} ^ {i - 2}a ^ j(\mathrm{mod}\,p) $$$$t \equiv a ^ {i - 1}X_1 + b\frac{1 - a ^ {i - 1}}{1 - a}(\mathrm{mod}\,p) $$$$t \equiv a ^ {i - 1}X_1 + \frac{b}{1 - a} - \frac{b}{1 - a} \cdot a^{i - 1}(\mathrm{mod}\,p) $$$$t \equiv a ^ {i - 1}(X_1 - \frac{b}{1 - a}) + \frac{b}{1 - a}(\mathrm{mod}\,p) $$$$a ^ {i - 1} \equiv \frac{t - \frac{b}{1 - a}}{X_1 - \frac{b}{1 - a}}(\mathrm{mod}\,p) $$

大功告成，用BSGS求解出$i - 1$的值，由于$t$是第$i$项，答案加一即可

Detail 1

对于$X_1 = t$时，直接输出$1$

Detail 2

对于$a = 0$时，$X_i = b$

Detail 3

对于$a = 1$时，有$X_i \equiv X_1 + b(i - 1)(\mathrm{mod}\,p)$ 那么求解$t - X_1 \equiv b(i - 1)(\mathrm{mod}\,p)$的系数$i - 1$即可 注意当答案就是$p$的时候不要再模$p$了

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>

using std::cin;
using std::cout;
using std::endl;

template <typename I>
inline void read(I& x)
{
    char c = getchar();
    for (; !isdigit(c); c = getchar());
    for (x = 0; isdigit(c); x = x * 10 + (c ^ 48), c = getchar());
}

long long NUMOFCASES, a, b, p, x, t, X, Y;

long long exp(long long b, int i, int p)
{
    long long r = 1;
    for (; i; i >>= 1, b = b * b % p)
        if (i & 1)
            r = r * b % p;
    return r;
}

long long gcd(long long a, long long b)
{
    return b ? gcd(b, a % b) : a;
}

long long inv(long long x, int MOD)
{
    return exp(x, MOD - 2, MOD);
}

long long bsgs(long long a, long long b, int MOD)
{
    a %= MOD, b %= MOD;
    std::map <long long, long long> map;
    register long long m = ceil(sqrt(MOD)), t = 1;
    for (register int i = 0; i < m; ++i)
    {
        if (!map.count(t))
            map[t] = i;
        t = t * a % MOD;
    }
    register long long k = inv(t, MOD), w = b;
    for (int i = 0; i < m; ++i)
    {
        if (map.count(w))
            return i * m + map[w];
        w = w * k % MOD;
    }
    return -1;
}

int main()
{
    read(NUMOFCASES);
    for (; NUMOFCASES; --NUMOFCASES)
    {
        read(p), read(a), read(b), read(x), read(t);
        if (x == t)
            cout << 1 << endl;
        else if (a == 1)
        {
            t = ((t - x) % p + p) % p;
            if (t % gcd(b, p))
                cout << -1 << endl;
            else
            {
                if ((t * inv(b, p) + 1) % p == 0)
                    cout << p << endl;
                else
                    cout << (t * inv(b, p) + 1) % p << endl;
            }
        }
        else if (a == 0)
        {
            if (b == t)
                cout << 2 << endl;
            else
                cout << -1 << endl;
        }
        else
        {
            long long ans = bsgs(a, ((t - b * inv(1 - a, p)) % p + p) % p * inv(((x - b * inv(1 - a, p)) % p + p) % p, p), p) % p;
            if (ans == -1)
                cout << -1 << endl;
            else
                cout << ans + 1 << endl;
        }
    }
}