来自两个阵列的共素对的计数小于O(n ^ 2)复杂度

Question

我在挑战中遇到了这个问题.有两个大小为N的阵列A和B,我们需要返回对的数量(A [i],B [j])where gcd(A[i],B[j])==1和A[i] != B[j].我只能想到几个测试用例超出时间限制的蛮力方法.

for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
        if(__gcd(a[i],b[j])==1) {
             printf("%d %d\n", a[i], b[j]);
        }
    }
}

你能建议时间有效的算法来解决这个问题.

编辑:无法分享问题链接,因为这是来自招聘挑战.我记得添加约束和输入/输出格式.

输入 -

• 第一行将包含N,即两个数组中存在的元素数.
• 第二行将包含N个空格分隔的整数,即数组A的元素.
• 第三行将包含N个空格分隔的整数,数组B的元素.

输出 -

• 根据条件对A [i],A [j]的对数.

约束 -

• 1 <= N <= 10 ^ 5
• 1 <A [i],B [j] <= 10 ^ 9其中i,j <N

Answer 1

第一步是使用Eratosthenes 筛法计算到sqrt(10^9). 然后可以使用此筛选器快速找到任何小于 的数的所有质因数10^9（请参阅getPrimeFactors(...)下面代码示例中的函数）。

接下来，对于每个A[i]具有质因子p0, p1, ..., pk，我们计算所有可能的子产品X-p0, p1, p0p1, p2, p0p2, p1p2, p0p1p2, p3, p0p3, ..., p0p1p2...pk并在 map 中计算它们cntp[X]。实际上，地图cntp[X]告诉我们A[i]可被 整除的元素数X，其中X是素数的 0 或 1 次幂的乘积。例如，对于数字A[i] = 12，素因数是2, 3。我们将计算cntp[2]++，cntp[3]++和cntp[6]++。

最后，对于每个B[j]具有质因子p0, p1, ..., pk，我们再次计算所有可能的子产品X并使用包含-排除原理来计算所有非互质对C_j（即与A[i]共享至少一个质因子的s的数量B[j]）。C_j然后从对的总数中减去这些数字-N*N以获得最终答案。

注意：包含-排除原则如下所示：

C_j = (cntp[p0] + cntp[p1] + ... + cntp[pk]) -
      (cntp[p0p1] + cntp[p0p2] + ... + cntp[pk-1pk]) +
      (cntp[p0p1p2] + cntp[p0p1p3] + ... + cntp[pk-2pk-1pk]) -
      ...

并解释了这样一个事实，即 incntp[X]和cntp[Y]我们可以将同一个数字计算A[i]两次，因为它可以被X和整除Y。

这是该算法的一个可能的 C++ 实现，它产生与 OP 的朴素 O(n^2) 算法相同的结果：

// get prime factors of a using pre-generated sieve
std::vector<int> getPrimeFactors(int a, const std::vector<int> & primes) {
    std::vector<int> f;
    for (auto p : primes) {
        if (p > a) break;
        if (a % p == 0) {
            f.push_back(p);
            do {
                a /= p;
            } while (a % p == 0);
        }
    }
    if (a > 1) f.push_back(a);

    return f;
}

// find coprime pairs A_i and B_j
// A_i and B_i <= 1e9
void solution(const std::vector<int> & A, const std::vector<int> & B) {
    // generate prime sieve
    std::vector<int> primes;
    primes.push_back(2);

    for (int i = 3; i*i <= 1e9; ++i) {
        bool isPrime = true;
        for (auto p : primes) {
            if (i % p == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            primes.push_back(i);
        }
    }

    int N = A.size();

    struct Entry {
        int n = 0;
        int64_t p = 0;
    };

    // cntp[X] - number of times the product X can be expressed
    // with prime factors of A_i
    std::map<int64_t, int64_t> cntp;

    for (int i = 0; i < N; i++) {
        auto f = getPrimeFactors(A[i], primes);

        // count possible products using non-repeating prime factors of A_i
        std::vector<Entry> x;
        x.push_back({ 0, 1 });

        for (auto p : f) {
            int k = x.size();
            for (int i = 0; i < k; ++i) {
                int nn = x[i].n + 1;
                int64_t pp = x[i].p*p;

                ++cntp[pp];
                x.push_back({ nn, pp });
            }
        }
    }

    // use Inclusion–exclusion principle to count non-coprime pairs
    // and subtract them from the total number of prairs N*N

    int64_t cnt = N; cnt *= N;

    for (int i = 0; i < N; i++) {
        auto f = getPrimeFactors(B[i], primes);

        std::vector<Entry> x;
        x.push_back({ 0, 1 });

        for (auto p : f) {
            int k = x.size();
            for (int i = 0; i < k; ++i) {
                int nn = x[i].n + 1;
                int64_t pp = x[i].p*p;

                x.push_back({ nn, pp });

                if (nn % 2 == 1) {
                    cnt -= cntp[pp];
                } else {
                    cnt += cntp[pp];
                }
            }
        }
    }

    printf("cnt = %d\n", (int) cnt);
}

活生生的例子

我无法估计的复杂性分析，但这里有我的笔记本电脑不同的一些剖析的结果N，均匀随机A[i]和B[j]：

For N = 1e2, takes ~0.02 sec
For N = 1e3, takes ~0.05 sec
For N = 1e4, takes ~0.38 sec
For N = 1e5, takes ~3.80 sec

为了进行比较，O(n^2) 方法采用：

For N = 1e2, takes ~0.00 sec
For N = 1e3, takes ~0.15 sec
For N = 1e4, takes ~15.1 sec
For N = 1e5, takes too long, didn't wait to finish