Submission #16913618


Source Code Expand

Copy
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def calc_div(N):
    sq = int(N**.5 + 10)
    x = np.arange(1, sq)
    x = x[N % x == 0]
    x = np.concatenate((x, N // x))
    return np.unique(x)

def inv_mod(a, mod):
    b, u, v = mod, 1, 0
    while b:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
    return u % mod

def main(N):
    N *= 2
    div = calc_div(N)
    for a in div:
        a = int(a)
        b = N // a
        if np.gcd(a, b) != 1:
            continue
        # b | an + 1
        n = (-inv_mod(a, b)) % b
        k = a * n
        if k == 0:
            k += N
        assert k * (k + 1) % N == 0
        yield k

N = int(read())
print(min(main(N)))

Submission Info

Submission Time
Task B - Sum is Multiple
User maspy
Language Python (3.8.2)
Score 600
Code Size 830 Byte
Status
Exec Time 818 ms
Memory 766772 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
× 2
× 42
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt
All 00-sample-01.txt, 00-sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt
Case Name Status Exec Time Memory
00-sample-01.txt 124 ms 26788 KB
00-sample-02.txt 125 ms 27072 KB
01-01.txt 122 ms 26752 KB
01-02.txt 527 ms 474088 KB
01-03.txt 701 ms 621588 KB
01-04.txt 525 ms 469036 KB
01-05.txt 813 ms 720324 KB
01-06.txt 604 ms 552920 KB
01-07.txt 519 ms 466700 KB
01-08.txt 637 ms 593824 KB
01-09.txt 484 ms 433408 KB
01-10.txt 734 ms 689872 KB
01-11.txt 686 ms 655688 KB
01-12.txt 749 ms 702984 KB
01-13.txt 795 ms 739888 KB
01-14.txt 628 ms 584624 KB
01-15.txt 816 ms 762276 KB
01-16.txt 567 ms 515296 KB
01-17.txt 378 ms 313348 KB
01-18.txt 731 ms 694832 KB
01-19.txt 658 ms 621552 KB
01-20.txt 501 ms 440476 KB
01-21.txt 486 ms 432108 KB
01-22.txt 646 ms 603032 KB
01-23.txt 544 ms 497228 KB
01-24.txt 818 ms 766772 KB
01-25.txt 795 ms 744856 KB
01-26.txt 456 ms 354884 KB
01-27.txt 524 ms 425632 KB
01-28.txt 586 ms 490812 KB
01-29.txt 604 ms 515496 KB
01-30.txt 646 ms 554688 KB
01-31.txt 734 ms 657632 KB
01-32.txt 753 ms 673196 KB
01-33.txt 805 ms 717428 KB
01-34.txt 417 ms 316272 KB
01-35.txt 294 ms 194000 KB
01-36.txt 586 ms 516656 KB
01-37.txt 296 ms 212152 KB
01-38.txt 477 ms 409632 KB
01-39.txt 226 ms 132884 KB
01-40.txt 298 ms 214152 KB