一个数组可以划分的最大子数组，使得不同子数组中任意两个元素的 GCD 始终为 1？

Question

给定< code>n，数组元素的数目和< code>arr[n]，数字数组，需要找到数组可以分成的子数组的最大数目，使得对于属于不同子数组的每个< code>a和< code>b，< code>GCD(a，b)=1。

例如:

5
2 3 4 5 6
Ans: 2 ----> {(2,3,4,6),(5)}

任何其他进一步分裂它的企图都不会满足这些条件。

我的方法：
1.对数组进行排序
2.继续计算元素的lcm
3.每当元素的gcd和之前元素的lcm为1时，增加计数器。

int main()
{
        int n;
        cin>>n;
        long long int arr[n];
        for(int i=0;i<n;++i)
            cin>>arr[i];
        sort(arr,arr+n);
        long long int ans=1,l=arr[n-1];
        for(int i=n-2;i>=0;i--)
        {
            if(gcd(l,arr[i])==1)
                ans++;
            l=lcm(l,arr[i]);
        }
        cout<<ans<<endl;
    return 0;
} 

在我的答案被多次判断为错误答案之后，我很困惑我的答案是否正确。由于n的限制为10^6，数组元素为10^7，因此解决方案失败的另一个原因是




Answer 1

我认为这就是您所指的问题：https://www.codechef.com/problems/CHEFGRUP

我的方法如下（我超过了时间限制）：

这可以使用埃拉托色尼筛来完成，复杂度将是O（nlog（log（n））其中n最多可以是10^7。

一旦我们有了所有需要的质数，这就可以非常有效地实现。

在这一步中需要注意的一点是，假设我们有两个数，其素数分解包含公共素数，那么这两个元素不能在不同的子数组中，因为GCD不会是1（如问题中所要求的）。因此，对于所有这些对，它们必须位于同一子阵列中。如何实现这一点？

我们可以创建一个所有素数的不相交集。所以开始时的集合数将是素数的数量。然后，在每次因式分解期间，我们将连接所有作为除数的素数，并将它们与原始数相加在同一个组中。这将对所有数字重复。

此外，我们必须检查一次，是否首先需要一些素数。因为在这一步之前，我们只是假设范围内的素数集一样多。但是有些可能未使用。因此，这可以通过遍历循环一次并找到唯一代表的数量来检查。这将是我们的答案。

我的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int prime[(int)1e7+10] = {0};

struct union_find {
    std::vector <int> parent, rank;

    // Constructor to initialse 'parent' and 'rank' vector.
    union_find(int n) {
        parent = std::vector <int> (n);
        rank = std::vector <int> (n, 0);        // initialse rank vector with 0.
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }

    // Find with Path Compression Heuristic.
    int find_(int a) {
        if(a == parent[a])
            return a;
        return parent[a] = find_(parent[a]);
    }

    // Union by checking rank to keep the depth of the tree as shallow as possible.
    void union_(int a, int b) {
        int aa = find_(a), bb = find_(b);
        if(rank[aa] < rank[bb])
            parent[aa] = bb;
        else
            parent[bb] = aa;
        if(rank[aa] == rank[bb])
            ++rank[aa];
    }
};

union_find ds(1e7+10);

int main() {
    int n;
    int sq = sqrt(1e7+10);
    for(int i = 4; i < 1e7+10; i += 2)
        prime[i] = 1;
    for(int i = 3; i <= sq; i += 2) {
        if(!prime[i]) {
            for(int j = i*i; j < 1e7+10; j += i)
                prime[j] = 1;
        }
    }

    vector <int> primes;
    primes.push_back(2);
    for(int i = 3; i < 1e7+10; i += 2) {
        if(!prime[i])
            primes.push_back(i);
    }


    scanf("%d", &n);
    int a[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    for(int i = 0; i < n; i++) {

        int temp = a[i];
        // int sq = sqrt(temp);
        vector <int> divisors;
        for(int j = 0; j < primes.size(); j++) {
            if(primes[j] > temp)
                break;
            if(temp % primes[j] == 0) {
                divisors.push_back(primes[j]);
                while(temp % primes[j] == 0) {
                    temp /= primes[j];
                }
            }
        }
        if(temp > 2)
            divisors.push_back(temp);

        for(int i = 1; i < divisors.size(); i++)
            ds.union_(divisors[i], divisors[i-1]);
        if(divisors.size() > 0)
            ds.union_(divisors[0], a[i]);
    }

    set <int> unique;
    for(int i = 0; i < n; i++) {
        int x = ds.find_(a[i]);
        unique.insert(x);
    }

    printf("%d\n", unique.size());
    return 0;
}