結果

問題 No.726 Tree Game
ユーザー kohei2019kohei2019
提出日時 2022-03-26 11:36:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,589 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 55,040 KB
最終ジャッジ日時 2024-10-15 03:31:35
合計ジャッジ時間 1,950 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
54,528 KB
testcase_01 AC 41 ms
54,528 KB
testcase_02 AC 41 ms
54,528 KB
testcase_03 AC 42 ms
54,272 KB
testcase_04 AC 42 ms
54,656 KB
testcase_05 AC 41 ms
54,656 KB
testcase_06 AC 42 ms
54,784 KB
testcase_07 AC 42 ms
54,784 KB
testcase_08 AC 41 ms
54,656 KB
testcase_09 WA -
testcase_10 AC 40 ms
54,656 KB
testcase_11 AC 41 ms
54,808 KB
testcase_12 AC 42 ms
54,656 KB
testcase_13 AC 42 ms
54,784 KB
testcase_14 AC 41 ms
54,656 KB
testcase_15 AC 41 ms
54,656 KB
testcase_16 AC 42 ms
54,528 KB
testcase_17 AC 40 ms
54,656 KB
testcase_18 AC 41 ms
54,656 KB
testcase_19 AC 40 ms
54,656 KB
testcase_20 AC 41 ms
54,784 KB
testcase_21 AC 41 ms
54,912 KB
testcase_22 AC 41 ms
54,528 KB
testcase_23 AC 42 ms
55,040 KB
testcase_24 AC 41 ms
54,656 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
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')
0