← 返回题目列表

AtCoder · agc067_c

C. 整除同态

中文机器翻译题面 查看原题

分数: 1100 点

问题陈述

我们称正整数的无限序列 (a_1,a_2,\cdots) 好 当且仅当满足以下两个条件时:

  • 存在一个有限常数 C 这样 a_n \le C \cdot n 对于所有人 1 \le n;

  • 对于所有正整数对 (n,m), a_n \mid a_m 当且仅当 n\mid m。在这里, x \mid y 意味着 x 划分 y.

给你一个正整数序列 A=(A_1,A_2,\cdots,A_N) 长度 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 or 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-st 测试用例,我们可以让 a_n=n 并且满足条件。