基本概括
当解决这个问题时,我们需要找到满足条件的整数 \(k\),使得对于给定的序列 \(A=(A_1,A_2,\dots,A_N)\) 中的每个数 \(A_i\),都满足 \(\gcd(A_i, k) = 1\)。
实现思路
首先,我们可以观察到,如果 \(k\) 是 \(A_i\) 的质因数或其倍数,那么 \(\gcd(A_i, k)\) 将不等于 1。因此,我们可以推断出,我们需要找到不是序列 \(A\) 中任何数的质因数或倍数的整数 \(k\)。
为了找到满足条件的整数 \(k\),我们可以使用质因数分解的思想。对于序列 \(A\) 中的每个数 \(A_i\),我们可以将其进行质因数分解,然后将分解得到的质因数及其倍数标记为不满足条件的。剩下的整数即为满足条件的整数 \(k\)。
实现过程
为了实现质因数分解和标记的过程,我们可以使用一个布尔数组 vis
来记录 \(1\) 到 \(m\) 之间的整数是否满足互质条件。初始化时,我们将 vis
数组的所有元素都设置为 true。
对于序列 \(A\) 中的每个数 \(A_i\),我们将其进行质因数分解。对于每个质因数 \(j\),我们将从 \(j\) 开始,递增地将 vis
数组中的对应整数位置设置为 false,保证不满足互质条件。注意要在循环中跳过已经被其他质因数标记的位置。
具体来说,对于每个 \(a_i\),我们从 \(2\) 开始遍历到 \(\sqrt{a_i}\),如果当前数能整除 \(a_i\),那么它就是 \(a_i\) 的一个质因子。我们将其标记在 vis
中对应位置的整数置为 false,然后不断除以这个质因子,直到 \(a_i\) 不再能整除这个质因子为止。如果 \(a_i\) 大于 \(1\),那么它本身也是一个质因子,我们将其标记在 vis 中对应位置的整数置为 false。这样,我们就完成了对于每个 \(a_i\) 的质因子的处理。
最后,我们遍历整数 \(1\) 到 \(m\),将 vis
的第 k 项设置为 true 的整数加入结果向量 ans
中。至此,我们找到了所有满足条件的整数。
在代码的最后,我们按照题目要求输出结果,首先输出结果向量 ans
的长度,然后逐行输出结果。
整体总结
整体而言,通过筛法的思想和质因数分解的方法,我们可以高效地找到满足条件的整数。
AC Code
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> a;
vector<int> ans;
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<bool> vis(m + 1, true);
for (int i = 0; i < n; i++) {
int num = a[i];
for (int j = 2; j * j <= num; j++) {
if (num % j == 0) {
while (num % j == 0) {
num /= j;
}
for (int k = j; k <= m; k += j) {
vis[k] = false;
}
}
}
if (num > 1) {
for (int k = num; k <= m; k += num) {
vis[k] = false;
}
}
}
for (int k = 1; k <= m; k++) {
if (vis[k]) {
ans.push_back(k);
}
}
cout << ans.size() << endl;
for (int k : ans) {
cout << k << endl;
}
return 0;
}//看在我写的如此详细,就点个赞吧
标签:满足条件,因数分解,abc215,int,整数,vis,我们
From: https://www.cnblogs.com/To-Carpe-Diem/p/17834605.html