[zerojudge] a223: 10298 - Power Strings

from sys import stdin
import math

'''
題目說 字串長度 <= 1000000
所以先來建立一個質數表
'''
limit = 1000000
u = int(math.sqrt(limit))
sieve = [0, 0, 2, 3] + [1] * (u - 4)
prime = [2]
for i in range(3, u, 2):
    if(sieve[i] == 0): 
        # sieve[i] 為 0 表示被篩掉了    
        continue
    prime.append(i)
    for j in range(i*i, u, i): 
        sieve[j] = 0
########

def fact(n): # 因數分解
    r = []
    k = math.sqrt(n)
    for x in prime:
        if(x > k): break
        # 檢查到 n 的平方根
        c = 0
        while(n % x == 0):
            c += 1
            n //= x
        if(c): r.append([x,c])
        # c 是試除的次數        
    if(n > 1): r.append([n,1])
    # 剩餘的數 > 1 必定是質因數
    return r

def expand(v, i): 
    if(i == len(prt)): return
    for h in range(prt[i][1]+1):
        tmp = v
        tmp *= prt[i][0] ** h
        f.add(tmp)
        expand(tmp, i+1)

for s in stdin: # 開始 input
    s = s.strip()
    if(s == '.'): break
    n = len(s) # 字串長度
    if(s[0] * n == s):
        # 如果出現 aaaaa 直接輸出 5
        print(n)
        continue
    prt = fact(n)
    # 先對字串長度做質因數分解
    # 如果 n = 6,  fact(6) = [[2,1],[3,1]]
    f = set()
    expand(1, 0)
    # 遞迴將 prt 展開為正因數
    # fact(6) = [[2,1],[3,1]] = [1,2,3,6]
    正因數表 = sorted(list(f))
    '''
    接下來要針對字串長度的正因數來比對
    1 就不用了，上面檢查過了
    '''
    for 長度 in 正因數表[1:]:
        檢查字串 = s[:長度]
        倍數 = n // 長度
        if(檢查字串 * 倍數 == s):
            print(倍數)
            break