Contest Duration: ~ (local time) (150 minutes) Back to Home

Submission #16913618

Source Code Expand

Copy
```import sys
import numpy as np

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

print(min(main(N)))```

#### Submission Info

Submission Time 2020-09-20 21:17:54+0900 B - Sum is Multiple maspy Python (3.8.2) 600 830 Byte AC 818 ms 766772 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
 AC × 2
 AC × 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