結果
| 問題 | No.3333 Consecutive Power Sum (Large) |
| コンテスト | |
| ユーザー |
 himueu
|
| 提出日時 | 2025-12-08 00:42:19 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,045 bytes |
| 記録 | |
| コンパイル時間 | 293 ms |
| コンパイル使用メモリ | 82,588 KB |
| 実行使用メモリ | 392,556 KB |
| 最終ジャッジ日時 | 2025-12-08 00:44:28 |
| 合計ジャッジ時間 | 112,384 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 62 TLE * 1 |
ソースコード
from math import isqrt
def miller_rabin(n, bases):
m = n - 1
e = (m & -m).bit_length() - 1
d = n >> e
for b in bases:
x = pow(b, d, n)
if x == 1:
continue
for _ in range(e):
y = pow(x, 2, n)
if y == 1:
if x == n - 1:
break
else:
return False
x = y
else:
return False
return True
def is_prime(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
if n < 2047:
return miller_rabin(n, [2])
if n < 9080191:
return miller_rabin(n, [31, 73])
if n < 4759123141:
return miller_rabin(n, [2, 7, 61])
if n < 1122004669633:
return miller_rabin(n, [2, 13, 23, 1662803])
if n < 3770579582154547:
return miller_rabin(n, [2, 880937, 2570940, 610386380, 4130785767])
if n < 18446744073709551617:
return miller_rabin(n, [2, 325, 9375, 28178, 450775, 9780504, 1795265022])
if n < 318665857834031151167461:
return miller_rabin(n, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37])
if n < 3317044064679887385961981:
return miller_rabin(n, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41])
return miller_rabin(n, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47])
def gcd(a, b):
while a:
a, b = b % a, a
return b
def find_prime_factor(n):
if n % 2 == 0:
return 2
m = int(n ** 0.125) + 1
for c in range(1, n):
def f(a):
return (pow(a, 2, n) + c) % n
y = 0
g = q = r = 1
k = 0
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 *= 2
if g == n:
g = 1
y = ys
while g == 1:
y = f(y)
g = gcd(abs(x - y), n)
if g == n:
continue
if is_prime(g):
return g
elif is_prime(n // g):
return n // g
else:
return find_prime_factor(g)
def prime_factorize(n):
from collections import defaultdict
res = defaultdict(int)
while not is_prime(n) and n > 1:
p = find_prime_factor(n)
s = 0
while n % p == 0:
n //= p
s += 1
res[p] = s
if n > 1:
res[n] = 1
return res
def divisors(ls):
res = [1]
for p, e in ls.items():
res = [r * p**k for r in res for k in range(e+1)]
return sorted(res)
n = int(input())
ls = prime_factorize(n)
m = 10 ** 24
me = next(i for i in range(m) if 2 ** i > n) + 1
ans = []
for e in range(1, me):
if e == 1:
ls[2] += 1
div = divisors(ls)
ld = (len(div) + 1) // 2
for i in range(ld):
a = div[i]
b = div[~i]
if a > b:
break
if (b - a) % 2:
l = (b - a - 1) // 2
r = (b + a - 1) // 2
ans.append((e, l+1, r))
elif e == 2:
ls[3] += 1
div = divisors(ls)
def f(a):
return a * (a + 1) * (a * 2 + 1)
def pred(l, w):
return f(l + w) - f(l) <= n * 6
for w in div:
if w ** 3 > n * 3:
break
ok = 0
ng = isqrt(n // w) + 1
while ng - ok > 1:
mid = (ok + ng) // 2
if pred(mid, w):
ok = mid
else:
ng = mid
l, r = ok, ok + w
if f(r) - f(l) == n * 6:
ans.append((e, l+1, r))
elif e == 3:
ls[2] += 1
ls[3] -= 1
div = divisors(ls)
def f(a):
return a**2 * (a + 1)**2
def pred(l, w):
return f(l + w) - f(l) <= n * 4
for w in div:
if w ** 4 > n * 4:
break
ok = 0
ng = int((n // w) ** 0.34) + 1
while ng - ok > 1:
mid = (ok + ng) // 2
if pred(mid, w):
ok = mid
else:
ng = mid
l, r = ok, ok + w
if f(r) - f(l) == n * 4:
ans.append((e, l+1, r))
else:
la = next(i for i in range(n) if i ** e > n) + 1
a = [i ** e for i in range(la+1)]
for i in range(la):
a[i+1] += a[i]
l = r = 0
while l < la:
while r < la and a[r] - a[l] < n:
r += 1
if a[r] - a[l] == n:
ans.append((e, l+1, r))
l += 1
ans.sort()
print(len(ans))
print("\n".join(f"{e} {l} {r}" for e, l, r in ans))