Игра

• 번역은 https://www.acmicpc.net/board/view/145743
• 나눴을때 최대공약수가 1이 되면 진다. 즉, 최대공약수를 2 이상으로 유지하면서 자기 수를 나누는 동작을 번갈아 가면서 할때, 상대보다 오랫동안 버티는 것이 목표이다. cold game의 느낌.
• A와 B의 최대공약수가 g1*g2*…g_k 라고 하자. 그러면 A=a1*a2*..*a_n*g1*g2*…g_k, B=b1*b2*..*b_m*g1*g2*…g_k 이다
• 내 턴에 g_i를 지우면, 상대방도 자신의 턴에 같은 g_i를 지울수 있다. 그래서 g_i를 지우는 것은 상대보다 오래 살아남는데에 도움이 안된다.
• 그러면 게임은 A는 a_i를 지우면서 버티고 B는 b_i를 지우면서 버틸때, 누가 더 오래 버틸수 있느냐이다. 결국 C이하인 a_i의 개수와 b_i의 개수를 비교해서 큰 쪽이 이기게 된다.
• 시간복잡도는 각각을 소인수분해하는데 걸리는 O(sqrt(max(A,B))) 이다

"""Solution code for "BOJ 29042. Игра".

- Problem link: https://www.acmicpc.net/problem/29042
- Solution link: http://www.teferi.net/ps/problems/boj/29042

Tags: [game theory]
"""

import math
from teflib import numtheory


def main():
    A, B, C = [int(x) for x in input().split()]

    g = math.gcd(A, B)
    a_score = sum(
        e
        for p, e in numtheory.prime_factorization_small(A // g).items()
        if p <= C
    )
    b_score = sum(
        e
        for p, e in numtheory.prime_factorization_small(B // g).items()
        if p <= C
    )

    print('First' if a_score > b_score else 'Second')


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_factorization_small