ARC137A - Coprime Pair

考え方

「$y-x$を大きい方から順に調べて，初めて$\gcd(x,y) = 1$となるものを出力すれば，制限時間内に止まるだろう」という方針でうまくいく．

コンテスト中に計算量まで考えるのはなかなか大変．
Editorial - AtCoder Regular Contest 137

回答例

$d$を$1$ずつ増やしながら，$y - x = (R - L) - d$を調べていく．

import math

L, R = map(int, input().split())
d = 0
while True:
  for r in range(d):
    for l in range(d - r):
      if math.gcd(R - r, L + l) == 1:
        exit(print((R - r) - (L + l)))
  d += 1