結果
問題 | No.1312 Snake Eyes |
ユーザー |
![]() |
提出日時 | 2020-12-09 00:18:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 694 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 61,952 KB |
最終ジャッジ日時 | 2024-11-30 12:55:53 |
合計ジャッジ時間 | 7,473 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 85 |
ソースコード
import sys from math import sqrt input = sys.stdin.readline N = int(input()) if N <= 2: print(N + 1) exit(0) res = N + 1 def make_divisors(n): lower_divisors , upper_divisors = [], [] i = 1 while i*i <= n: if n % i == 0: lower_divisors.append(i) if i != n // i: upper_divisors.append(n//i) i += 1 return lower_divisors + upper_divisors[::-1] divs = make_divisors(N)[: - 1] for i in divs: q = (N - i) // i if N % q == N // q: res = min(res, q) for p in range(2, int(sqrt(N)) + 1): x = N r = x % p while x: if x % p != r: break x -= r x //= p else: res = min(res, p) break print(res)