Round Corridor (Codeforces 1200C)
Tags: Math, number theory

Amugae is in a very large round corridor. The corridor consists of two areas. The inner area is equally divided by $$$n$$$ sectors, and the outer area is equally divided by $$$m$$$ sectors. A wall exists between each pair of sectors of same area (inner or outer), but there is no wall between the inner area and the outer area. A wall always exists at the 12 o'clock position.  The inner area's sectors are denoted as $$$(1,1), (1,2), \dots, (1,n)$$$ in clockwise direction. The outer area's sectors are denoted as $$$(2,1), (2,2), \dots, (2,m)$$$ in the same manner. For a clear understanding, see the example image above.Amugae wants to know if he can move from one sector to another sector. He has $$$q$$$ questions.For each question, check if he can move between two given sectors.

Input: The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 10^{18}$$$, $$$1 \le q \le 10^4$$$) — the number of sectors in the inner area, the number of sectors in the outer area and the number of questions.Each of the next $$$q$$$ lines contains four integers $$$s_x$$$, $$$s_y$$$, $$$e_x$$$, $$$e_y$$$ ($$$1 \le s_x, e_x \le 2$$$; if $$$s_x = 1$$$, then $$$1 \le s_y \le n$$$, otherwise $$$1 \le s_y \le m$$$; constraints on $$$e_y$$$ are similar). Amague wants to know if it is possible to move from sector $$$(s_x, s_y)$$$ to sector $$$(e_x, e_y)$$$.

Output: For each question, print "YES" if Amugae can move from $$$(s_x, s_y)$$$ to $$$(e_x, e_y)$$$, and "NO" otherwise.You can print each letter in any case (upper or lower).

Note: Example is shown on the picture in the statement.

Sample Inputs:
4 6 3
1 1 2 3
2 6 1 2
2 6 2 4

Sample Outputs:
YES
NO
YES

Solution (Python):
from math import gcd
((n, m, _), *q) = [[*map(int, s.split())] for s in open(0)]
g = gcd(n, m)
for (a, b, c, d) in q:
    print((b - 1) // (n // g if a == 1 else m // g) == (d - 1) // (n // g if c == 1 else m // g) and 'YES' or 'NO')

Solution (Python):
from sys import stdin
from math import ceil

def gcd(a, b):
    if b:
        return gcd(b, a % b)
    else:
        return a

def sno(g, n, y):
    return -(-y // (n // g))
(n, m, q) = map(int, stdin.readline().split())
g = gcd(n, m)
for i in range(q):
    (sx, sy, ex, ey) = map(int, stdin.readline().split())
    (one, two) = (0, 0)
    if sx == 1:
        one = sno(g, n, sy)
    else:
        one = sno(g, m, sy)
    if ex == 1:
        two = sno(g, n, ey)
    else:
        two = sno(g, m, ey)
    if one == two:
        print('YES')
    else:
        print('NO')

Solution (Python):
import math
(n, m, q) = list(map(int, input().split()))
hcf = math.gcd(n, m)
d = [0, n // hcf, m // hcf]
for i in range(q):
    (sx, sy, ex, ey) = list(map(int, input().split()))
    ps = (sy - 1) // d[sx]
    pe = (ey - 1) // d[ex]
    if ps == pe:
        print('YES')
    else:
        print('NO')