题解 P3306 【[SDOI2013]随机数生成器】

· · 题解

个人博客

欢迎大佬互换友链

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;
        }
    }
}