結果

問題 No.3001 ヘビ文字列
ユーザー 👑 rin204rin204
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from math import gcd
def MillerRabin(n):
if n <= 1:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
if n < 4759123141:
A = [2, 7, 61]
else:
A = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
s = 0
d = n - 1
while d % 2 == 0:
s += 1
d >>= 1
for a in A:
if a % n == 0:
return True
x = pow(a, d, n)
if x != 1:
for t in range(s):
if x == n - 1:
break
x = x * x % n
else:
return False
return True
def pollard(n):
# https://qiita.com/t_fuki/items/7cd50de54d3c5d063b4a
if n % 2 == 0:
return 2
m = int(n**0.125) + 1
step = 0
while 1:
step += 1
def f(x):
return (x * x + step) % n
y = k = 0
g = q = r = 1
while g == 1:
x = y
while k < 3 * r // 4:
y = f(y)
k += 1
while k < r and g == 1:
ys = y
for _ in range(min(m, r - k)):
y = f(y)
q = q * abs(x - y) % n
g = gcd(q, n)
k += m
k = r
r <<= 1
if g == n:
g = 1
y = ys
while g == 1:
y = f(y)
g = gcd(abs(x - y), n)
if g == n:
continue
if MillerRabin(g):
return g
elif MillerRabin(n // g):
return n // g
else:
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 //= p
if 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) + 1
return ret
S = list(input())
n = len(S)
P = set(primefact(n))
mi = n + 1
x = -1
cnt = [0] * 26
for p in P:
tot = n
p = n // p
for s in range(p):
for i in range(s, n, p):
cnt[ord(S[i]) - 65] += 1
tot -= max(cnt)
for i in range(s, n, p):
cnt[ord(S[i]) - 65] -= 1
if tot < mi:
mi = tot
x = p
p = x
for s in range(p):
for i in range(s, n, p):
cnt[ord(S[i]) - 65] += 1
c = ""
ma = -1
for 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] -= 1
S[i] = c
print(*S, sep="")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0