标签： BSGS

$$ \text{设数列}X_i\text{的生成函数为}T\left( z \right) \\ \text{则}T\left( z \right) =azT\left( x \right) +\frac{z^2b}{1-z}+x_1z \\ T\left( z \right) =\frac{x_1z+\left( b-x_1 \right) z^2}{\left( 1-az \right) \left( 1-z \right)} \\ \text{设}Q\left( z \right) =az^2+\left( -1-a \right) z+\text{1,}Q`\left( z \right) =2az-\left( a+1 \right) \\ Q`\left( \frac{1}{\rho} \right) =\frac{2a}{\rho}-\left( a+1 \right) \\ \text{设}P\left( z \right) =x_1z+\left( b-x_1 \right) z^2 \\ a_i=\frac{-x_1-\frac{b-x_1}{\rho ^{}}}{\frac{2a}{\rho}-\left( a+1 \right)}=\frac{\rho x_1+\left( b-x_1 \right)}{\rho \left( a+1 \right) -2a} \\ \text{根据有理生成函数展开式，在}a\ne \text{1时,有}\rho _1=a,\rho _2=\text{1,}a_i=\frac{\rho x_1+\left( b-x_1 \right)}{\rho \left( a+1 \right) -2a} \\ \text{整理得} \\ X_n=a^n\frac{ax_1-x_1+b}{a^2-a}-\frac{b}{a-1} \\ X_n+\frac{b}{a-1}=a^n\frac{ax_1-x_1+b}{a^2-a} \\ a^n=\frac{X_n\left( a^2-a \right) +ab}{ax_1-x_1+b} \\ BSGS\text{即可} \\ a=\text{1时} \\ X_n=X_1+\left( n-1 \right) b,\text{直接求解即可} \\ \frac{X_n-X_1}{b}+1=n $$

#include <iostream>
#include <cmath>
#include <unordered_map>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

int_t mod;
int_t power(int_t base, int_t index)
{
    const int_t phi = mod - 1;
    index = (index % phi + phi) % phi;
    base = (base % mod + mod) % mod;
    int_t result = 1;
    while (index)
    {
        if (index & 1)
            result = result * base % mod;
        index >>= 1;
        base = base * base % mod;
    }
    return result;
}

int_t logMod(int_t a, int_t b)
{
    a %= mod;
    b %= mod;
    if (a == 0)
        return -1;
    int_t sqr = sqrt(mod - 1) + 3;
    std::unordered_map<int_t, int_t> memory;
    for (int_t i = 1; i <= sqr; i++)
    {
        int_t curr = b * power(a, -i) % mod;
#ifdef DEBUG
        cout << b << " * " << a << "^(-" << i << ") = " << curr << " at i = " << i << endl;
#endif
        if (memory.count(curr))
        {
            memory[curr] = std::min(memory[curr], i);
        }
        else
        {
            memory[curr] = i;
        }
    }
    for (int_t i = 0; i <= sqr; i++)
    {
        int_t curr = power(a, sqr * i);
        if (memory.count(curr) && memory[curr] + sqr * i > 0)
        {
            return memory[curr] + sqr * i;
        }
    }
    return -1;
}
int_t process()
{
    int_t a, b, x1, t;
    cin >> mod >> a >> b >> x1 >> t;
    {
        int_t prev = x1;
        for (int_t i = 2; i <= 10; i++)
        {
            if (prev == t)
                return i - 1;
            prev = (a * prev + b) % mod;
        }
    }
    if (a == 1)
    {
        int_t binv = power(b, -1);
        if (binv == 0)
            return -1;
        return ((t - x1 + 2 * mod) * binv % mod + 1) % mod;
    }
    int_t right = (t * (a * a % mod - a + mod) % mod + a * b % mod) % mod * power(a * x1 % mod - x1 + b, -1) % mod;
#ifdef DEBUG

    cout << "right=" << right << endl;
#endif
    return logMod(a, right);
}
int main()
{
    int_t T;
    cin >> T;
    for (int_t i = 1; i <= T; i++)
    {
        cout << process() << endl;
#ifdef DEBUG
        cout << endl
             << endl;
#endif
    }
    return 0;
}