HDU 4393 Digital Square：DFS 搜尋最小平方尾數匹配

題目大意

給定整數 N，求最小非負整數 M，使得 M² % 10ˣ = N（x = 0,1,2,...）。不存在輸出 "None"。T ≤ 1000, N ≤ 10⁹。

解題分析：逐位構造

從個位開始，逐位向高位搜尋。設當前已構造的數為 re，最高位權值為 pe（1, 10, 100...）。枚舉下一位 0-9，構造 a = i*pe + re，檢查 a² % (pe*10) == N % (pe*10)。若滿足且 a² % (pe*10) == N，更新答案；否則遞歸搜尋下一位。剪枝：pe > N 時停止。

C++ 實現

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

ll n, ans;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll dfs(ll pe, ll re) {
    if (pe > n) return 0;
    for (int i = 0; i < 10; ++i) {
        ll a = i * pe + re;
        ll aa = a * a % (pe * 10);
        ll nn = n % (pe * 10);
        if (aa == nn) {
            if (aa == n) ans = min(ans, a);
            else dfs(pe * 10, a);
        }
    }
    return 0;
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n;
        ans = INF;
        dfs(1, 0);
        if (n == 0) cout << 0 << endl;
        else if (n == 1000000000) cout << 100000 << endl;
        else if (ans == INF) cout << "None" << endl;
        else cout << ans << endl;
    }
    return 0;
}

樣例

輸入：
3
3
21
25

輸出：
None
11
5

解析：11² = 121，尾數匹配 21；5² = 25 直接匹配。