mathgame

Hà và Ngọc thay phiên nhau chơi một trò chơi, Hà bắt đầu trước.

Ban đầu, có một số N trên bảng. Ở lượt của mỗi người chơi, người chơi đó phải:

• Chọn bất kỳ một số x với 0 <x <N và N% x == 0.
• Thay thế số N trên bảng phấn bằng N - x.

Nếu người chơi không thể chọn bất kì một số nào thoả mãn, người đó sẽ thua trò chơi.

Giả sử 2 người chơi đều chọn các con số để tối ưu hoá khả năng chiến thắng của mình. Trả về 1 khi và chỉ khi Hà thắng trò chơi, nếu Hà không thắng, trả về 0.

Ví dụ

• Với n = 2, đầu ra là mathGame (n) = 1.
  Hà chọn 1 và Ngọc không thể chọn thêm số nào.
• Với n = 3, đầu ra là mathGame (n) = 0.
  Hà chọn 1, Ngọc chọn 1 và Hà không thể chọn thêm số nào.

Đầu vào/Đầu ra

• [giới hạn thời gian chạy] 1 giây 

• [đầu vào] integer n

  Điều kiện tiền đề:
  1 ≤ n ≤ 109

• [đầu ra] integer
  Trả về 1 khi và chỉ khi Hà thắng trò chơi, nếu Hà không thắng, trả về 0.