問題は以下のように定式化することができます。

• 全ての \(1\le i\le N\) に対し \(x \equiv A_i \bmod B_i\) を満たすような非負整数 \(x\) は存在するか？

まず、 \(\displaystyle B=\prod_{k=1}^n p_k^{e_k}\) とすると \(x \equiv A \bmod B\) という条件は全ての \(1\le k\le n\) に対し \(\displaystyle x \equiv A \bmod p_k^{e_k}\) が成り立つことと同値です。これを元に条件を分解していくことで、 \(B_i\) の素因数が全て \(1\) つであるような場合に帰着させることができます。さらに、中国剰余定理より \(B\) の持つ \(1\) つの素因数の値が違うもの同士は問題の答えの Yes / No に関与しないので、素因数毎に独立に問題を考えて良いことも分かります。以降はある素因数 \(p\) を固定し、 \(B\) が全て \(p^{e_k}\) で表せる場合を考えます。

全ての \(1\le i\le m\) に対し \(\displaystyle x \equiv A_i \bmod p^{e_i}\) を満たすような非負整数 \(x\) は存在するか？という問題を考えます。 \(i_0\) を \(e_i\) が最大となる \(i\) とすると、この問題は以下と同値であることが分かります。

• 全ての \(1\le i\le m\) に対し以下が成立するか？
  • \(\displaystyle x \equiv A_i \bmod p^{e_i}\) と \(\displaystyle x \equiv A_{i_0}\bmod p^{e_{i_0}}\) を両方満たすような非負整数 \(x\) が存在する。

\(m\) 個の条件を同時に考えるような問題から、 \(2\) つの条件のみを考える問題を \(m\) 回解く問題に帰着させることができます。

\(\displaystyle x \equiv A_i \bmod p^{e_i}\) と \(\displaystyle x \equiv A_{i_0}\bmod p^{e_{i_0}}\) を両方満たすような非負整数 \(x\) が存在することは \(A_i \equiv A_{i_0}\bmod p^{e_{i_0}}\) が成り立つことと同値であるので、この式を用いて簡単に判定することができます。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

INF = 10**6 + 1
pr = [True] * INF
pr[0] = pr[1] = False
g = [[] for _ in range(INF)]
for p in range(2, INF):
    if not pr[p]:
        continue
    for pp in range(p, INF, p):
        pr[pp] = False
        cnt = 0
        np = pp
        while np % p == 0:
            cnt += 1
            np //= p
        g[pp].append((p, cnt))
li = [[] for _ in range(INF)]

n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    for p, cnt in g[b]:
        li[p].append((a % (p**cnt), cnt))

for p in range(INF):
    if len(li[p]) == 0:
        continue
    d = dict()
    ma_a, ma_cnt = -1, -1
    for a, cnt in li[p]:
        if cnt in d:
            if d[cnt] != a:
                print("No")
                exit()
        else:
            d[cnt] = a
        if cnt > ma_cnt:
            ma_a = a
            ma_cnt = cnt
    for a, cnt in li[p]:
        if ma_a % (p**cnt) != a:
            print("No")
            exit()
print("Yes")