C - Divisibility Homomorphism

Contest Duration: 2024-08-18(Sun) 12:00 - 2024-08-18(Sun) 15:00 (local time) (180 minutes) Back to Home

C - Divisibility Homomorphism Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $1100$ 点

問題文

正整数の無限列 $(a_1,a_2,\cdots)$ が以下の条件をともに満たすとき、またそのときに限りそれを良いと呼びます。

ある有限の定数 $C$ が存在し、すべての $1 \le n$ について $a_n \le C \cdot n$ である。
すべての正整数の組 $(n,m)$ に対し、 $a_n \mid a_m$ と $n\mid m$ とは同値である。ここで、 $x \mid y$ は $x$ が $y$ を割り切ることを表す。

長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N)$ が与えられます。 $(A_1,A_2,\cdots,A_N)$ で始まる良い無限列が存在するか判定してください。

解くべきテストケースは $T$ 個あります。

制約

$1\le T \le 5000$
$1 \leq N \leq 5000$
$1 \leq A_i \leq 10^{18}$
ひとつの入力の中のテストケースすべてにわたる $N$ の総和は $5000$ 以下である。
すべての入力値は整数である。

入力

入力は標準入力から以下の形式で与えられる。

 $T$ 
 $case_1$ 
 $case_2$ 
 $\vdots$ 
 $case_T$

各テストケースは以下の形式で与えられる。

 $N$ 
 $A_1$   $A_2$   $\cdots$   $A_N$

出力

各テストケースについて、 $(A_1,A_2,\cdots,A_N)$ で始まる良い無限数列が存在するなら Yes、そうでないなら No と出力せよ。
Yes または No の出力において、各文字は大文字・小文字のいずれでもよい。

入力例 1Copy

Copy

5
5
1 2 3 4 5
5
1 4 9 16 25
5
1 4 6 8 10
5
1 2 4 4 5
5
1 2 3 5 4

出力例 1Copy

Copy

Yes
Yes
Yes
No
No

$1$ 番目のテストケースについて、 $a_n=n$ とでき、これは条件を満たします。

Score : $1100$ points

Problem Statement

We call an infinite sequence of positive integers $(a_1,a_2,\cdots)$ good if and only if it satisfies both of the following conditions:

There exists a finite constant $C$ such that $a_n \le C \cdot n$ for all $1 \le n$ ;
For all pairs of positive integers $(n,m)$ , $a_n \mid a_m$ if and only if $n\mid m$ . Here, $x \mid y$ means $x$ divides $y$ .

You are given a positive integer sequence $A=(A_1,A_2,\cdots,A_N)$ of length $N$ . Check if there exists a good infinite sequence starting with $(A_1,A_2,\cdots,A_N)$ .

You have $T$ testcases to solve.

Constraints

$1\le T \le 5000$
$1 \leq N \leq 5000$
$1 \leq A_i \leq 10^{18}$
The sum of $N$ across the test cases in a single input is at most $5000$ .
All input values are integers.

Input

Input is given from Standard Input in the following format:

 $T$ 
 $case_1$ 
 $case_2$ 
 $\vdots$ 
 $case_T$

Each test case is given in the following format:

 $N$ 
 $A_1$   $A_2$   $\cdots$   $A_N$

Output

For each test case, if there exists a good infinite sequence starting with $(A_1,A_2,\cdots,A_N)$ , print Yes, and otherwise print No. In printing Yes or No, you can output each letter in any case (upper or lower).

Sample Input 1Copy

Copy

5
5
1 2 3 4 5
5
1 4 9 16 25
5
1 4 6 8 10
5
1 2 4 4 5
5
1 2 3 5 4

Sample Output 1Copy

Copy

Yes
Yes
Yes
No
No

For the $1$ -st test case, we can let $a_n=n$ and that satisfies the condition.