ZeroJudge 解題筆記：c658. 小新的提款卡密碼

作者：王一哲
日期：2025年8月19日


ZeroJudge 題目連結：c658. 小新的提款卡密碼

解題想法

先列出 1 ~ $10^{10}$ 之間的完全平方數 sq，將 sq 之中數字 0 ~ 9 的數量組成字串 dig，用字典儲存資料，以 dig 作為 key，以 sq 作為 value。讀取測資時，直接從表格中找出對應的答案，如果不在表格之中則印出 0。

Python 程式碼

使用時間約為 1.2 s，記憶體約為 16 MB，通過測試。

import sys

def digits(num):  # 計算整數 0 ~ 9 的數量
    cnt = [0]*10  # 計數器
    for c in num: cnt[int(c)] += 1  # 從 nu 依序讀取字元 c 計算數量
    return "".join([str(i) for i in cnt])  # 取出 cnt 的資料組成字串再回傳

table = dict()  # 各種 0 ~ 9 出現數量對應的完全平方數
for i in range(1, 100000):  # 題目最大到 1E10，表格只要算 1 ~ 100000-1
    sq = i*i  # i 平方
    dig = digits(str(sq))  # 轉成 0 ~ 9 的數量字串
    if dig not in table: table[dig] = [sq]  # 如果 dig 不在 table 之中，新增 [sq]
    else: table[dig].append(sq)  # 反之，串列加入 sq

for line in sys.stdin:  # 讀取字串直到 EOF 為止
    dig = digits(line.strip())  # 計算 0 ~ 9 的數量
    if dig not in table: print(0)  # 如果 dig 不在 table 之中印出 0
    else: print(*table[dig])  # 反之印出 table[dig]

C++ 程式碼

使用時間約為 0.2 s，記憶體約為 5.2 MB，通過測試。

#include <iostream>
#include <string>
#include <map>
#include <vector>
typedef long long LL;
using namespace std;

string digits(string num) {  // 計算整數 0 ~ 9 的數量
    int cnt[10] = {0};  // 計數器
    for(char c : num) cnt[c-'0']++;  // 從 num 依序讀取字元 c 計算數量
    string t = "";  // 儲存回傳值用的空字串
    for(int i=0; i<10; i++) t += char(cnt[i]+'0');  // 取出 cnt 的資料組成字串再回傳
    return t;
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0);
    map<string, vector<LL>> table;  // 各種 0 ~ 9 出現數量對應的完全平方數
    for(int i=1; i<100000; i++) {  // 題目最大到 1E10，表格只要算 1 ~ 100000-1
        LL sq = (LL)i*(LL)i;  // i 平方
        string dig = digits(to_string(sq));  // 轉成 0 ~ 9 的數量字串
        table[dig].push_back(sq);  // 新增 sq
    }
    string line;
    while(cin >> line) {  // 讀取字串直到 EOF 為止
        string dig = digits(line);  // 計算整數 0 ~ 9 的數量
        if (table.count(dig) == 0) {  // 如果 dig 不在 table 之中印出 0
            cout << "0\n";
        } else {  // 反之印出 table[dig]
            for(int i=0; i<(int)table[dig].size(); i++) {
                cout << table[dig][i] << " \n"[i == (int)table[dig].size()-1];
            }
        }
    }
    return 0;
}