#1184493 (PyPy3) No.3690 Only One

• 問題: No.3690 Only One
• ユーザー: nasutarou1341
• 提出日時: 2026-09-06 19:38:06
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 63 ms / 2,000 ms
• コード長: 2,683 bytes
• コンパイル時間: 261 ms
• コンパイル使用メモリ: 95,820 KB
• 実行使用メモリ: 78,976 KB
• 最終ジャッジ日時: 2026-09-06 19:38:09
• 合計ジャッジ時間: 2,493 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 14

ソースコード

import math
class Prime:
  def __init__(self, N: int = 1):
    self.N = N
    self.lpf, self.prime = self.makeLpf(N)
  def getPrimeList(self):
    """素数リスト(Nまで)"""
    return self.prime
  def isPrime(self, x : int):
    """素数判定"""
    if x > self.N: return self.isPrimeBig(x)
    return self.lpf[x] == x
  def primeFactorization(self, x: int):
    """素因数分解"""
    if x > self.N: return self.primeFactrizationBig(x)
    else: return self.primeFactrizationSmall(x)
  def makeLpf(self, N: int):
    """前計算O(N)"""
    lpf = [0] * (N + 1)
    prime = []
    for i in range(2, N + 1):
      if lpf[i] == 0:
        lpf[i] = i
        prime.append(i)
      for p in prime:
        if p > lpf[i]: break
        j = i * p
        if j > N: break
        lpf[j] = p
    return lpf, prime
  def isPrimeBig(self, x):
    """素数判定"""
    if x <= 1: return False
    if x == 2: return True
    if x % 2 == 0: return False
    if x < 4759123141: return self.millerRabin(x, [2, 7, 61])
    return self.millerRabin(x, [2, 325, 9375, 28178, 450775, 9780504, 1795265022])
  def millerRabin(self, n, L):
    """ミラーラビン法"""
    s = 0
    d = n - 1
    while d % 2 == 0:
      s += 1
      d >>= 1
    for a in L:
      if n <= a: return True
      x = pow(a, d, n)
      if x != 1:
        for t in range(s):
          if x == n - 1: break
          x = x * x % n
        else: return False
    return True
  def primeFactrizationSmall(self, x):
    """前計算O(N), クエリO(素因数の数)で素因数分解"""
    p = {}
    while x != 1:
      n = self.lpf[x]
      if n in p: p[n] += 1
      else: p[n] = 1
      x = x // n
    return p
  def primeFactrizationBig(self, x):
    """O(√x)で素因数分解"""
    p = {}
    last = math.floor(x ** 0.5)
    if x % 2 == 0:
      p[2] = 1
      x //= 2
      while x & 1 == 0:
        x //= 2
        p[2] += 1
    for i in range(3, last + 1, 2):
      if x % i == 0:
        x //= i
        p[i] = 1
        while x % i == 0:
          x //= i
          p[i] += 1
    if x != 1:
      p[x] = 1
    return p
  def tau(self, N):
    if N == 1: return 1
    plist = self.primeFactorization(N)
    v = list(plist.values())
    if max(v) == 1:
      n = len(v)
      if n % 2: return -1
      else: return 1
    else: return 0
  def tausum(self, N):
    data = [1] * (N + 1)
    data[0] = 0
    for i in range(2, N + 1):
      if not self.isPrime(i): continue
      x = i * i
      for j in range(i, N + 1, i):
        if j % x == 0: data[j] = 0
        else: data[j] *= -1
    return sum(data)

A, B = list(map(int, input().split()))
x = math.gcd(A, B)

if x == 1:
  print(1)
else:
  print(0)