結果

問題 No.3333 Consecutive Power Sum (Large)
コンテスト
ユーザー maspy
提出日時 2025-11-02 22:42:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 8,680 ms / 10,000 ms
コード長 4,176 bytes
コンパイル時間 285 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 230,424 KB
最終ジャッジ日時 2025-11-02 22:44:00
合計ジャッジ時間 105,893 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 63
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
sample で WA が出ているが手元で再現してない
yandexcup があるのでここで終わりで
"""


def gcd(a, b):
    while a:
        a, b = b % a, a
    return b


def is_prime(n):
    if n == 2:
        return 1
    if n == 1 or n % 2 == 0:
        return 0

    m = n - 1
    lsb = m & -m
    s = lsb.bit_length()-1
    d = m // lsb

    test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]

    for a in test_numbers:
        if a == n:
            continue
        x = pow(a, d, n)
        r = 0
        if x == 1:
            continue
        while x != m:
            x = pow(x, 2, n)
            r += 1
            if x == 1 or r == s:
                return 0
    return 1


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 factorize(n):
    res = {}
    while not is_prime(n) and n > 1:  # nが合成数である間nの素因数の探索を繰り返す
        p = find_prime_factor(n)
        s = 0
        while n % p == 0:  # nが素因数pで割れる間割り続け、出力に追加
            n //= p
            s += 1
        res[p] = s
    if n > 1:  # n>1であればnは素数なので出力に追加
        res[n] = 1
    return res


ANS = []

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

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

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


N = int(input())

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

pfs = factorize(N)

if 2 not in pfs:
    pfs[2] = 0
if 3 not in pfs:
    pfs[3] = 0


def get_divs(pfs):
    n = 1
    for p, e in pfs.items():
        n *= e + 1
    divs = [1] * n
    n = 1
    for p, e in pfs.items():
        add = n * e
        for i in range(add):
            divs[n+i] = divs[i]*p
        n += add
    return divs


pfs[2] += 1
for d in get_divs(pfs):
    # 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))

pfs[2] -= 1

# E=2
# 項数が 6N の約数
pfs[2] += 1
pfs[3] += 1
N6 = N * 6
for d in get_divs(pfs):
    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
    if 0 <= x:
        L = x+1
        R = x+d
        ANS.append((2, L, R))
    #    print(a, b, c, sq)
pfs[2] -= 1
pfs[3] -= 1


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 get_divs(pfs):
    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))
        x = L
        for _ in range(E - 1):
            x *= L
        S -= x

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