結果

問題 No.3333 Consecutive Power Sum (Large)
コンテスト
ユーザー maspy
提出日時 2025-11-02 22:10:42
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,747 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 67,952 KB
最終ジャッジ日時 2025-11-02 22:10:56
合計ジャッジ時間 6,816 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 63
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sympy
import random


ANS = []

"""
E=1 を解く
流石に約数列挙は必要になる

E=1 の解法から E=3 の解は作れている

E=2 も約数列挙を使う
"""

N = int(input())

divs = sympy.ntheory.divisors(2 * N)


for d in divs:
    # E = 1
    b = d
    a = (2*N)//b
    if a <= b and (a + b) % 2 == 1:
        R = (a+b-1) // 2
        L = (b-a+1) // 2
        ANS.append((1, L, R))

N6 = N * 6
# E=2
# 項数が 6N の約数
for d in range(1, 150_000_000):
    if d*(d-1)*(2*d-1) > N6:
        break
    if (N6 % d != 0):
        continue
    a = 6
    b = 6 * d + 6
    c = 2 * d * d + 3 * d + 1 - (N6 // d)
    D = b * b - 4 * a * c
    if D < 0:
        continue
    # 精度心配だったっけ
    sq = int(D ** .5)
    if sq * sq != D:
        continue
    if (sq-b) % 12 != 0:
        continue
    x = (-b+sq)//12
    L = x+1
    R = x+d
    ANS.append((2, L, R))
    #    print(a, b, c, sq)


def f(S):
    # n(n+1)/2==S
    X = 8 * S + 1
    x = int(X**.5)
    if x*x != X:
        return -1
    # 2n+1==x
    return (x-1)//2


# E=3
for d in divs:
    if d % 2 != 0:
        continue
    d //= 2  # div of N
    a = d
    b = N//d
    if a > b or (a+b) % 2 != 0:
        continue
    SR = (a+b)//2
    SL = (b-a)//2
    R = f(SR)
    L = f(SL)
    if L != -1 and R != -1:
        ANS.append((3, L+1, R))

# E は 4 以上です
for E in range(4, 80):
    S = 0
    R = 0
    for L in range(1, 10_000_000):
        while 1:
            x = R**E
            if S + x > N:
                break
            R += 1
            S += x
        if L == R:
            break
        if S == N:
            ANS.append((E, L, R - 1))
        S -= L**E

ANS.sort()
print(len(ANS))
for a, b, c in ANS:
    print(a, b, c)
0