seuOJ523 - Good Array

题目类型：传统
输入文件：标准输入流
输出文件：标准输出流
时间限制：1000 ms
空间限制：1024 MiB
题目标签：Div.1, 2025

题目描述

对于一个长度为 $n$ 的数组 $a$ 和一个正整数 $m$ ，称数组 $a$ 是好的当存在一个正整数 $b$ ，使得所有小于等于 $m$ 的正整数中，有且仅有在数组 $a$ 中出现的那些是 $b$ 的因子。

例如，当 $a=[1,2,3],m=5$ 的时候就是一个好的数组，因为可以选取 $b=6$ 。但是当 $a=[2,3],m=5$ 的时候就不是一个好的数组，因为当 $b=6$ 的时候，数组 $a$ 中缺少了 $b$ 的一个因子 $1$ 。当 $a=[1,2,3,4],m=6$ 时不能选取 $b=4$ ，因为数组 $a$ 中的数字 $3$ 不是 $b$ 的一个因子。

给定一个长度为 $n$ 的数组 $a$ 和一个正整数 $m$ ，请判断 $a$ 的每一个前缀是否是一个好的数组。

输入格式

第一行，一个整数 $t(1\le t\le 2\times 10^4)$ ，代表数据组数。

对于每组数据：

第一行，两个整数 $n,m(1\le n \le 10^5;1\le m\le 10^7)$ ，代表数组 $a$ 的长度， $m$ 的含义与题目中一致。

第二行，一个长度为 $n$ 的数组 $a_1,\dots,a_n(1\le a_i\le m)$ ，代表数组 $a$ 。

保证同一测试点内 $n$ 的总和不超过 $10^5$ 。

输出格式

对于每组数据，输出一个长度为 $n$ 的二进制字符串 $s$ 。如果 $s_i=1$ 代表数组 $a$ 长度为 $i$ 的前缀是一个好的数组；如果 $s_i=0$ 代表数组 $a$ 长度为 $i$ 的前缀不是一个好的数组。

样例

输入样例

4
6 16
2 1 4 6 3 12
8 10000000
1 2 8 4 16 9999995 1024 1
3 5
3 2 1
3 6
3 2 1

输出样例

样例解释
样例第一组数据中，对于数组 $a$ 的每一个前缀， $b$ 的值分别为 $0,2,4,0,0,24$ （ $0$ 代表 $b$ 的值不存在）。