結果
問題 | No.726 Tree Game |
ユーザー | kohei2019 |
提出日時 | 2022-03-26 11:38:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 4,643 bytes |
コンパイル時間 | 346 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 54,784 KB |
最終ジャッジ日時 | 2024-10-15 03:34:19 |
合計ジャッジ時間 | 2,239 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
54,528 KB |
testcase_01 | AC | 42 ms
54,272 KB |
testcase_02 | AC | 42 ms
54,528 KB |
testcase_03 | AC | 42 ms
54,784 KB |
testcase_04 | AC | 42 ms
54,784 KB |
testcase_05 | AC | 41 ms
54,400 KB |
testcase_06 | AC | 41 ms
54,144 KB |
testcase_07 | AC | 45 ms
54,528 KB |
testcase_08 | AC | 41 ms
54,656 KB |
testcase_09 | AC | 41 ms
54,784 KB |
testcase_10 | AC | 42 ms
54,272 KB |
testcase_11 | AC | 42 ms
54,784 KB |
testcase_12 | AC | 42 ms
54,656 KB |
testcase_13 | AC | 42 ms
54,528 KB |
testcase_14 | AC | 41 ms
54,272 KB |
testcase_15 | AC | 43 ms
54,528 KB |
testcase_16 | AC | 43 ms
54,656 KB |
testcase_17 | AC | 41 ms
54,784 KB |
testcase_18 | AC | 42 ms
54,400 KB |
testcase_19 | AC | 42 ms
54,400 KB |
testcase_20 | AC | 43 ms
54,400 KB |
testcase_21 | AC | 42 ms
54,656 KB |
testcase_22 | AC | 42 ms
54,656 KB |
testcase_23 | AC | 42 ms
54,656 KB |
testcase_24 | AC | 43 ms
54,784 KB |
ソースコード
import math import random class Prime: seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] def is_prime(self, n): """ prime test (hybrid) see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369 :param n: :return: boolean """ is_prime_common = self.is_prime_common(n) if is_prime_common is not None: return is_prime_common if n < 2000000: return self.is_prime_brute_force(n) else: return self.is_prime_miller_rabin(n) def is_prime_common(self, n): if n == 1: return False if n in Prime.seed_primes: return True if any(map(lambda x: n % x == 0, self.seed_primes)): return False def is_prime_brute_force(self, n): """ brute force prime test use with is_prime_common if you want to skip seed_primes :param n: :return: boolean """ for k in range(2, int(math.sqrt(n)) + 1): if n % k == 0: return False return True def is_prime_miller_rabin(self, n): """ miller rabin prime test use with is_prime_common if you want to skip seed_primes see also algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59 improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369 :param n: :return: boolean """ d = n - 1 while d & 1 == 0: d >>= 1 # use one of these lines / upper is more efficient. witnesses = self.get_witnesses(n) # witnesses = [random.randint(1, n - 1) for _ in range(100)] for w in witnesses: y = pow(w, d, n) while d != n - 1 and y != 1 and y != n - 1: y = (y * y) % n d <<= 1 if y != n - 1 and d & 1 == 0: return False return True def get_witnesses(self, num): def _get_range(num): if num < 2047: return 1 if num < 1373653: return 2 if num < 25326001: return 3 if num < 3215031751: return 4 if num < 2152302898747: return 5 if num < 3474749660383: return 6 if num < 341550071728321: return 7 if num < 3825123056546413051: return 9 return 12 return self.seed_primes[:_get_range(num)] def gcd(self, a, b): if a < b: return self.gcd(b, a) if b == 0: return a while b: a, b = b, a % b return a @staticmethod def f(x, n, seed): """ pseudo prime generator :param x: :param n: :param seed: :return: pseudo prime """ p = Prime.seed_primes[seed % len(Prime.seed_primes)] return (p * x + seed) % n def find_factor(self, n, seed=1): """ find one of factor of n this function is based to Pollard's rho algorithm see also algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98 :param n: :param seed: :return: factor """ if self.is_prime(n): return n x, y, d = 2, 2, 1 count = 0 while d == 1: count += 1 x = self.f(x, n, seed) y = self.f(self.f(y, n, seed), n, seed) d = self.gcd(abs(x - y), n) if d == n: return self.find_factor(n, seed+1) return self.find_factor(d) def find_factors(self, n): primes = {} if self.is_prime(n): primes[n] = 1 return primes while n > 1: factor = self.find_factor(n) primes.setdefault(factor, 0) primes[factor] += 1 n //= factor return primes Y,X = map(int,input().split()) p = Prime() if p.is_prime(Y) and p.is_prime(X): print('Second') exit() if X == 2 or Y == 2: print('Second') exit() for i in range(100): if p.is_prime(Y+i+1): Yp=Y+i+1 break for i in range(100): if p.is_prime(X+i+1): Xp=X+i+1 break cn = (Yp-Y-1)+(Xp-X-1) print('Second' if cn % 2==0 else 'First')