102153: [AtCoder]ABC215 D - Coprime 2
Description
Score : $400$ points
Problem Statement
Given a sequence of $N$ positive integers $A=(A_1,A_2,\dots,A_N)$, find every integer $k$ between $1$ and $M$ (inclusive) that satisfies the following condition:
- $\gcd(A_i,k)=1$ for every integer $i$ such that $1 \le i \le N$.
Constraints
- All values in input are integers.
- $1 \le N,M \le 10^5$
- $1 \le A_i \le 10^5$
Input
Input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$
Output
In the first line, print $x$: the number of integers satisfying the requirement.
In the following $x$ lines, print the integers satisfying the requirement, in ascending order, each in its own line.
Sample Input 1
3 12 6 1 5
Sample Output 1
3 1 7 11
For example, $7$ has the properties $\gcd(6,7)=1,\gcd(1,7)=1,\gcd(5,7)=1$, so it is included in the set of integers satisfying the requirement.
On the other hand, $9$ has the property $\gcd(6,9)=3$, so it is not included in that set.
We have three integers between $1$ and $12$ that satisfy the condition: $1$, $7$, and $11$. Be sure to print them in ascending order.
Input
题意翻译
有一个长度为 $N$ 的序列 $A$，$A=(A_1,A_2,…,A_N)$ 和一个整数 $M$。 请求出有多少的 $k(1\leqslant k\leqslant M)$ 满足对于所有的 $i(1\leqslant i\leqslant N)$，$\gcd(a_i,k)=1$。 $1\leqslant N,M\leqslant 10^5$，$1\leqslant a_i\leqslant 10^6$。Output
问题描述
给定一个由 $N$ 个正整数构成的序列 $A=(A_1,A_2,\dots,A_N)$，找出满足以下条件的每一个整数 $k$（在 $1$ 到 $M$ 之间，包括 $1$ 和 $M$）：
- 对于每一个整数 $i$，满足 $1 \le i \le N$，都有 $\gcd(A_i,k)=1$。
约束条件
- 输入中的所有值都是整数。
- $1 \le N,M \le 10^5$
- $1 \le A_i \le 10^5$
输入
输入数据将从标准输入中以以下格式给出：
$N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$
输出
首先，打印 $x$：满足要求的整数的数量。
在接下来的 $x$ 行中，按升序打印满足要求的整数，每行一个。
样例输入 1
3 12 6 1 5
样例输出 1
3 1 7 11
例如，$7$ 满足 $\gcd(6,7)=1,\gcd(1,7)=1,\gcd(5,7)=1$，因此它包含在满足要求的整数集合中。
另一方面，$9$ 满足 $\gcd(6,9)=3$，因此它不包含在那个集合中。
在 $1$ 到 $12$ 之间，有三个满足条件的整数：$1$，$7$ 和 $11$。请确保按照升序打印它们。