테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Игра ======

===== 풀이 =====
  * 번역은 [[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))) 이다
  

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:numtheory#prime_factorization_small|teflib.numtheory.prime_factorization_small]]

{{tag>BOJ ps:problems:boj:골드_5}}