結果
問題 | No.3001 ヘビ文字列 |
ユーザー |
👑 |
提出日時 | 2025-01-05 02:43:23 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,679 bytes |
コンパイル時間 | 645 ms |
コンパイル使用メモリ | 82,188 KB |
実行使用メモリ | 314,084 KB |
最終ジャッジ日時 | 2025-01-05 02:45:05 |
合計ジャッジ時間 | 95,748 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 82 TLE * 1 |
ソースコード
from math import gcddef MillerRabin(n):if n <= 1:return Falseelif n == 2:return Trueelif n % 2 == 0:return Falseif n < 4759123141:A = [2, 7, 61]else:A = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]s = 0d = n - 1while d % 2 == 0:s += 1d >>= 1for a in A:if a % n == 0:return Truex = pow(a, d, n)if x != 1:for t in range(s):if x == n - 1:breakx = x * x % nelse:return Falsereturn Truedef pollard(n):# https://qiita.com/t_fuki/items/7cd50de54d3c5d063b4aif n % 2 == 0:return 2m = int(n**0.125) + 1step = 0while 1:step += 1def f(x):return (x * x + step) % ny = k = 0g = q = r = 1while g == 1:x = ywhile k < 3 * r // 4:y = f(y)k += 1while k < r and g == 1:ys = yfor _ in range(min(m, r - k)):y = f(y)q = q * abs(x - y) % ng = gcd(q, n)k += mk = rr <<= 1if g == n:g = 1y = yswhile g == 1:y = f(y)g = gcd(abs(x - y), n)if g == n:continueif MillerRabin(g):return gelif MillerRabin(n // g):return n // gelse:return pollard(g)def primefact(n):res = []while n > 1 and not MillerRabin(n):p = pollard(n)while n % p == 0:res.append(p)n //= pif n != 1:res.append(n)return sorted(res)def primedict(n):P = primefact(n)ret = {}for p in P:ret[p] = ret.get(p, 0) + 1return retS = list(input())n = len(S)P = set(primefact(n))mi = n + 1x = -1cnt = [0] * 26for p in P:tot = np = n // pfor s in range(p):for i in range(s, n, p):cnt[ord(S[i]) - 65] += 1tot -= max(cnt)for i in range(s, n, p):cnt[ord(S[i]) - 65] -= 1if tot < mi:mi = totx = pp = xfor s in range(p):for i in range(s, n, p):cnt[ord(S[i]) - 65] += 1c = ""ma = -1for i in range(26):if cnt[i] > ma:ma = cnt[i]c = chr(i + 65)for i in range(s, n, p):cnt[ord(S[i]) - 65] -= 1S[i] = cprint(*S, sep="")