题解

我们需要根据给定的序列预测下一个伪随机数。该序列由以下递推关系生成： [ x_{k+1} = (A \times x_k) \mod 47 ]

其中，$x_{k+1}$ 是当前数 $x_k$ 的下一个数，$A$ 是一个非负整数且小于 $1,000,000$ 的常数。给定一个序列 $x_1, x_2, \ldots, x_M$，我们需要预测 $x_{M+1}$。

1. 数据不足的情况：

   • 如果序列长度 $M = 1$，即只有一个数，无法确定 $A$，因此无法预测下一个数。

2. 确定常数 $A$：

   • 对于序列中的每一对连续的数 $(x_k, x_{k+1})$，解方程 $x_{k+1} = (A \times x_k) \mod 47$ 来找到可能的 $A$。
   • 若 $x_k = 0$，则 $x_{k+1}$ 也必须为 0，否则序列无效。
   • 否则，计算 $x_k$ 和 47 的最大公约数 $d$。如果 $d$ 不整除 $x_{k+1}$，则序列无效。
   • 计算 $x_k / d$ 在模 $47 / d$ 下的逆元，进而求出 $A$ 的可能值。

3. 验证 $A$ 的一致性：

   • 检查所有可能的 $A$ 是否满足整个序列的递推关系。
   • 如果多个 $A$ 满足条件，但它们预测的下一个数不同，则无法唯一确定下一个数。

4. 预测下一个数：

   • 如果找到唯一的 $A$，则计算 $x_{M+1} = (A \times x_M) \mod 47$。
   • 如果所有 $x_k$ 均为 0，则下一个数也是 0。

解决代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int mod_inverse(int a, int m) {
    a = a % m;
    for (int x = 1; x < m; x++) {
        if ((a * x) % m == 1) {
            return x;
        }
    }
    return -1; // 逆元不存在
}

void solve() {
    int M;
    cin >> M;
    vector<int> seq(M);
    for (int i = 0; i < M; ++i) {
        cin >> seq[i];
    }
    
    if (M == 1) {
        cout << "Dalsi cislo nelze urcit." << endl;
        return;
    }
    
    bool possible = true;
    int A = -1;
    
    for (int i = 0; i < M - 1; ++i) {
        int xk = seq[i];
        int xk1 = seq[i+1];
        
        if (xk == 0) {
            if (xk1 != 0) {
                possible = false;
                break;
            }
            continue;
        }
        
        int gcd_val = __gcd(xk, 47);
        if (gcd_val != 1) {
            if ((xk1 % gcd_val) != 0) {
                possible = false;
                break;
            }
        }
        
        int inv_xk = mod_inverse(xk / gcd_val, 47 / gcd_val);
        if (inv_xk == -1) {
            possible = false;
            break;
        }
        int ak = (xk1 / gcd_val) * inv_xk % (47 / gcd_val);
        
        if (i == 0) {
            int step = 47 / gcd_val;
            A = -1;
            bool found = false;
            for (int t = 0; t < step; ++t) {
                int candidate_A = ak + t * step;
                if (candidate_A >= 0 && candidate_A < 1000000) {
                    bool valid = true;
                    for (int j = 0; j < M - 1; ++j) {
                        int xj = seq[j];
                        int pred = (candidate_A * xj) % 47;
                        if (pred != seq[j+1]) {
                            valid = false;
                            break;
                        }
                    }
                    if (valid) {
                        if (A == -1) {
                            A = candidate_A;
                            found = true;
                        } else {
                            int next1 = (A * seq.back()) % 47;
                            int next2 = (candidate_A * seq.back()) % 47;
                            if (next1 != next2) {
                                possible = false;
                                break;
                            }
                        }
                    }
                }
            }
            if (!found) {
                possible = false;
            }
            if (!possible) break;
        }
    }
    
    if (!possible) {
        cout << "Algoritmus byl zmenen." << endl;
    } else {
        if (A == -1) {
            cout << "Vsad na 0." << endl;
        } else {
            int next_num = (A * seq.back()) % 47;
            cout << "Vsad na " << next_num << "." << endl;
        }
    }
}

int main() {
    int N;
    cin >> N;
    while (N--) {
        solve();
    }
    return 0;
}

代码解释

1. 模逆元计算：

   • mod_inverse 函数计算 $a$ 在模 $m$ 下的逆元，用于解方程 $A \times x_k \equiv x_{k+1} \mod 47$。

2. 处理输入数据：

   • 读取序列长度 $M$ 和序列本身。

3. 特殊情况处理：

   • 如果 $M = 1$，直接输出无法确定下一个数。

4. 求解常数 $A$：

   • 遍历序列中的每一对连续的数，验证其是否满足递推关系，并尝试求解 $A$。
   • 使用模逆元来解方程，并检查所有可能的 $A$ 是否一致。

5. 输出结果：

   • 根据验证结果输出预测的下一个数、算法被更改或无法确定下一个数。