首页 > 其他分享 >AT_abc215_d

AT_abc215_d

时间:2023-11-15 19:47:42浏览次数:37  
标签:满足条件 因数分解 abc215 int 整数 vis 我们

基本概括

当解决这个问题时,我们需要找到满足条件的整数 \(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

相关文章

  • [ABC215D] Coprime 2
    题目大意给定一个长度为\(n\)的数列\(a\),要求出\(1\simm\)中与\(a\)中的所有元素互质的数。数据范围:\(1\\leq\n,m\\leq\10^5,1\\leq\a_i\\leq\10^5\)。思路模拟赛加强了数据,卡了\(\mathcal{O}(n\sqrt{n})\),于是来写一个\(\mathcal{O}(n\logn)\)的。考......
  • [ABC215D] Coprime 2 题解
    题意给定数列\(A_N\)和一个正整数\(M\),求出所有的\(1\lek\leM\)满足\(\foralli\in\left[1,N\right],\gcd(k,A_i)=1\)。题解本题存在线性复杂度算法。记\(\operatorname{lpf}(n)=[1<n]\min\{p:p\midn\}+[1=n]\),即\(n\)的最小质因数。特别地,\(n......
  • AT_abc215_d 题解
    洛谷链接&Atcoder链接本篇题解为此题较简单做法及较少码量,并且码风优良,请放心阅读。题目简述给定\(N\),\(M\)及含有\(N\)个整数的序列\(A\)。求\(1\simM\)中与所有\(a_i\)均互质的整数及个数。思路首先说一下最开始的想法。直接暴力枚举\(1\simM\)的数,再分......
  • ABC215E 题解
    前言题目传送门!更好的阅读体验?萌萌DP题。思路题目就是在说从\(a\)里面按顺序掏出来一些字母,使得相同的字母都是相邻的(比如AABBBBCD可行,AAABBCAA不行)。看起来很不可做,突破口在于\(\text{A}\sim\text{J}\)一共只有\(10\)个字母,考虑状压。设\(dp_{i,s}\)表示......