/ 
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 の出力において、各文字は大文字・小文字のいずれでもよい。
入力例 1
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
出力例 1
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 1
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 1
Yes Yes Yes No No
For the 1-st test case, we can let a_n=n and that satisfies the condition.