AT_abc270_g [ABC270G] Sequence in mod P 题解

HappyJaPhy · 2023-12-03 09:43:27 · 题解

• [ABC270G] Sequence in mod P
• 博客阅读可能体验更佳

  题意

• 给出递推式如下，求最小的使 X_i=G 成立的 i。 S&i=0\\ (A\times X_{i-1}+B)\bmod p&i\ge1 \end{cases}

分析

• 这里分几种情况来分析：当 A=0 时，X_i 要么等于 S，要么等于 B，直接判断即可；当 A=1 时，X_i 为等差数列，通项公式为 X_i=(S+i\times B)\bmod p，于是求解同余方程 S+i\times B\equiv G\pmod p 即可。
• 最后一种情况，当 A\ge2 时，根据高中的一些知识我们可以知道，这个是可以转化成一个等比数列的。待定系数 C 有 X_i+C\equiv A(X_{i-1}+C)\pmod p，解得 C=(A-1)^{-1}\cdot B\bmod p。令 Y_i=(X_i+C)\bmod p，那么 Y_i\equiv A^i\cdot Y_0\equiv A^i\cdot(S+C)\pmod p。因此原问题转化为关于 i 的同余方程 G+C\equiv A^i\cdot(S+C)\pmod p 是否有解和最小正整数解的问题了。这是离散对数问题，利用大步小步算法求解即可。

大步小步算法（BSGS）

• 用于求解形如方程 A^x\equiv B\pmod p 的离散对数问题，其基于 meet-in-the-middle 的思想，复杂度 \tilde{O}(\sqrt n)。
• 首先因为 A^{x+n(p-1)}\equiv A^x(A^{p-1})^n\equiv A^x\pmod p，所以如果原方程有解，则在 [0,n-2] 的范围也一定有解。
• 我们拆分 x，令 B=\lceil\sqrt p\rceil，则一定存在 0\le L,R\le B 使得 x=L\cdot B-R。此时方程转化为求解 0\le L,R\le B 满足 A^{LB}\equiv B\cdot A^R\pmod p
• 根据这个式子，我们先预处理出 S=\left\{(A^B)^L\bmod p|0\le L\le B\right\} 中的所有值，然后对于每一个 0\le R\le B 计算出 B\cdot A^R\bmod p 并判断是否在集合 S 中即可。

代码

#include <bits/stdc++.h>
#define int long long
#define inf 1e10
using namespace std;
int a, b, s, g, p;
int A, B, C;

inline void read(int &x) {
    char ch = x = 0;
    int m = 1;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - 48;
        ch = getchar();
    }
    x *= m;
    return ;
}

inline void print(int x) {
    if (x < 0) putchar('-'), x = -x;
    static int stk[50];
    int top = 0;
    do {
        stk[top++] = x % 10;
        x /= 10;
    } while (x);
    while (top) {
        putchar(stk[--top] + 48);
    }
    putchar('\n');
    return ;
}

inline int ksmi(int a, int b, int p) {
    a %= p;
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

inline int BSGS(int a, int b, int p) {
    a %= p, b %= p;
    if (b == 1 || a == b) return b != 1;
    map<int, int> mp;
    int B = ceil(sqrt(p)), res = inf;
    for (int i = B; i; i--) {
        mp[ksmi(a, i * B, p)] = i * B;
    }
    for (int i = 0; i <= B; i++) {
        if (mp.find(b * ksmi(a, i, p) % p) != mp.end()) {
            res = min(res, mp[b * ksmi(a, i, p) % p] - i);
        }
    }
    if (res == inf) {
        return -1;
    } else {
        return res;
    }
}

signed main() {
    int T;
    read(T);
    while (T--) {
        read(p), read(a), read(b), read(s), read(g);
        if (s == g) print(0);
        else if (a == 0) {
            if (b == g) print(1);
            else print(-1);
        } else if (a == 1) {
            if (b == 0) print(-1);
            else {
                int x = ((g - s) % p + p) % p * ksmi(b, p - 2, p) % p;
                print(x);
            }
        } else if (s == 0 && b == 0) {
            print(-1);
        } else {
            A = a, C = ksmi(A - 1, p - 2, p) * b % p;
            B = ksmi(s + C, p - 2, p) * ((g + C) % p) % p;
            print(BSGS(A, B, p));
        }
    }
    return 0;
}