Vika and Price Tags
Contest: Codeforces Round 885 (Div. 2)
Difficulty rating: 1800
Tags: math, number theory

Vika came to her favorite cosmetics store "Golden Pear". She noticed that the prices of $$$n$$$ items have changed since her last visit.

She decided to analyze how much the prices have changed and calculated the difference between the old and new prices for each of the $$$n$$$ items.

Vika enjoyed calculating the price differences and decided to continue this process.

Let the old prices be represented as an array of non-negative integers $$$a$$$, and the new prices as an array of non-negative integers $$$b$$$. Both arrays have the same length $$$n$$$.

In one operation, Vika constructs a new array $$$c$$$ according to the following principle: $$$c_i = |a_i - b_i|$$$. Then, array $$$c$$$ renamed into array $$$b$$$, and array $$$b$$$ renamed into array $$$a$$$ at the same time, after which Vika repeats the operation with them.

For example, if $$$a = [1, 2, 3, 4, 5, 6, 7]$$$; $$$b = [7, 6, 5, 4, 3, 2, 1]$$$, then $$$c = [6, 4, 2, 0, 2, 4, 6]$$$. Then, $$$a = [7, 6, 5, 4, 3, 2, 1]$$$; $$$b = [6, 4, 2, 0, 2, 4, 6]$$$.

Vika decided to call a pair of arrays $$$a$$$, $$$b$$$ dull if after some number of such operations all elements of array $$$a$$$ become zeros.

Output "YES" if the original pair of arrays is dull, and "NO" otherwise.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of items whose prices have changed.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the old prices of the items.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$) — the new prices of the items.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output "YES" if the pair of price arrays is dull, and "NO" otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the array $$$a$$$ is initially zero.

In the second test case, after the first operation $$$a = [1, 2, 3], b = [0, 0, 0]$$$. After the second operation $$$a = [0, 0, 0], b = [1, 2, 3]$$$.

In the third test case, it can be shown that the array $$$a$$$ will never become zero.

Example input:
9
4
0 0 0 0
1 2 3 4
3
1 2 3
1 2 3
2
1 2
2 1
6
100 23 53 11 56 32
1245 31 12 6 6 6
7
1 2 3 4 5 6 7
7 6 5 4 3 2 1
3
4 0 2
4 0 2
3
2 5 2
1 3 4
2
6 1
4 2
2
0 0
0 3

Example output:
YES
YES
NO
NO
YES
YES
NO
YES
YES

Editorial:
First of all, if $$$a_i$$$ and $$$b_i$$$ are both zero, then all numbers in the sequence will be zero.
Otherwise, if one of the numbers $$$a_i, b_i$$$ is not zero, then if $$$a_i \ge b_i$$$, after one operation, the sum $$$a_i - b_i + b_i = a_i$$$ will decrease relative to the original value, or if $$$b_i > a_i$$$, after two operations, the sum $$$b_i - a_i + a_i = b_i$$$ will also decrease relative to the original value. Since the sum of non-negative integers cannot decrease infinitely, eventually one of the numbers $$$a_i, b_i$$$ will become zero. Let the first such moment occur after $$$cnt_i$$$ operations. Then, notice that now zeros will alternate with a period of $$$3$$$. Therefore, in the problem, we need to check that all $$$cnt_i$$$ have the same remainder when divided by $$$3$$$. Thus, the problem reduces to finding $$$cnt_i$$$ for each pair of non-zero $$$a_i, b_i$$$ modulo $$$3$$$.
Solution 1: Without loss of generality, assume $$$a_i \ge b_i$$$, otherwise apply one operation. Then, the sequence of numbers will have the form: $$$(a_i, b_i, a_i - b_i, a_i - 2 \cdot b_i, b_i, a_i - 3 \cdot b_i, a_i - 4 \cdot b_i, b_i, \ldots)$$$. Let $$$a_i = k \cdot b_i + r$$$. Then, using simple formulas, we can find the first moment when the neighboring pair of numbers becomes $$$r$$$ and $$$b_i$$$ in some order, and then simply find the answer for them. Thus, the problem can be solved using the generalized Euclidean algorithm.
Solution 2: We will build the sequence from the end. Let's find the first moment when we obtain $$$0$$$. Before this zero, there is some number $$$d$$$. It can be easily proven that $$$d$$$ is exactly equal to $$$gcd(a_i, b_i)$$$. Now, let's divide each number in the sequence by $$$d$$$, and obtain a new sequence of numbers, where the last number is zero and the penultimate number is $$$1$$$. Then, let's denote even numbers as $$$0$$$ and odd numbers as $$$1$$$. In this way, the sequence can be uniquely reconstructed from the end: $$$(0, 1, 1, 0, 1, 1, 0, 1, 1, \ldots)$$$. Thus, we can determine the remainder $$$cnt_i$$$ modulo $$$3$$$ by looking at the pair $$$(a_i / d, b_i / d)$$$ modulo $$$2$$$.
The complexity of both solutions will be $$$O(n \cdot \log{a_i})$$$.