ZeroJudge 解題筆記：a223. 10298 - Power Strings

作者：王一哲
日期：2025年12月26日


ZeroJudge 題目連結：a223. 10298 - Power Strings

解題想法

題目敘述的 $a*b$ 指的應該是字串 $a$ 之後接上字串 $b$，而 $a^n$ 指的是將$n$ 個字串 $a$ 接在一起，例如 $a = ABC$，則 $a^3 = ABCABCABC$。因此解題時，先找出這個字串 $s$ 長度 $n$ 所有的質因數 fac，然後由小到大測試每個質因數 $f$，取 $s[:f]$ 為子字串 $t$，檢查 $n//f$ 個 $t$ 相接之後是否等於 $s$，如果相等則 $n//f$ 就是答案；如果所有質因數都不合，則答案為 1。

Python 程式碼

使用時間約為 75 ms，記憶體約為 30.8 MB，通過測試。

import sys

def factor(s):
    n = len(s)
    fac = set()
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            fac.add(i)
            fac.add(n//i)
    return sorted(fac)

def solve(s, fac):
    n = len(s)
    for f in fac:
        b = s[:f]
        t = b*(n//f)
        if t == s: return n//f
    return 1

for line in sys.stdin:
    s = line.strip()
    if s == ".": break
    fac = factor(s)
    print(solve(s, fac))

C++ 程式碼

C++ 的 set 速度比較慢，使用時間約為 0.8 s，記憶體約為 85.2 MB，通過測試。

#include <iostream>
#include <string>
#include <set>
#include <cmath>
using namespace std;

void factor(string s, set<int>& fac) {
    int n = (int)s.size();
    for(int i=1; i<=int(sqrt(n)); i++) {
        if (n%i == 0) {
            fac.insert(i);
            fac.insert(n/i);
        }
    }
}

int solve(string s, set<int>& fac) {
    int n = (int)s.size();
    for(auto f : fac) {
        string b = s.substr(0, f);
        string t = "";
        for(int i=0; i<n/f; i++) t += b;
        if (t == s) return n/f;
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    while(cin >> s) {
        if (s == ".") break;
        set<int> fac;
        factor(s, fac);
        cout << solve(s, fac) << "\n";
    }
    return 0;
}