題目大意

給定整數 N，求最小非負整數 M，滿足 M² % 10ˣ = N（x=0,1,2,3...）。若不存在輸出 None。多測試用例（T ≤ 1000），N ≤ 10⁹。

樣例：

Input:  3  21  25
Output: None  11  5

解釋：11² = 121，末兩位 21 匹配；5² = 25 匹配；3 無解。

核心觀察

判斷幾位數相乘後對余數無影響即可。利用 BFS 從低位向高位構建答案，優先隊列保證最小值優先展開。

代碼實現（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int t, n;
long long Mod;

struct Node {
    long long num; // 當前構建的數
    long long ten; // 10 的冪次，用於模運算
    friend bool operator<(Node a, Node b) { return a.num > b.num; } // 小頂堆
} a, b;

void bfs() {
    priority_queue<Node> q;
    int last_digit = n % 10;
    // 枚舉個位數字 0-9，找出平方末位等於 last_digit 的數
    for (int i = 0; i < 10; i++) {
        if (i * i % 10 == last_digit) {
            a.num = i;
            a.ten = 10;
            q.push(a);
        }
    }
    while (!q.empty()) {
        a = q.top(); q.pop();
        // 檢查當前數是否滿足條件
        if (a.num * a.num % Mod == n) {
            cout << a.num << endl;
            return;
        }
        // 向高位擴展：在當前數左側添加一位數字 0-9
        for (int i = 0; i < 10; i++) {
            b.num = i * a.ten + a.num;
            b.ten = a.ten * 10;
            // 剪枝：新數的平方模 b.ten 必須等於 n 模 b.ten
            if (b.num * b.num % b.ten == n % b.ten) {
                q.push(b);
            }
        }
    }
    cout << "None" << endl;
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        Mod = 1;
        int nn = n;
        while (nn) { Mod *= 10; nn /= 10; } // Mod = 10^(位數)
        if (n == 0) { cout << 0 << endl; continue; } // 特判 0
        bfs();
    }
    return 0;
}

算法複雜度

• 時間：每位最多擴展 10 個分支，位數 ≤ 10，極快
• 空間：優先隊列存儲狀態，極小