小于O(n ^ 2)复杂度的两个数组的互质对数 [英] Count of co-prime pairs from two arrays in less than O(n^2) complexity
问题描述
我在一个挑战中遇到了这个问题.有两个数组A和B,它们的大小均为N,我们需要返回对数(A [i],B [j]),其中 gcd(A [i],B [j])==1
和 A [i]!= B [j]
.我只能想到暴力测试方法在几个测试用例中都超过了时间限制.
I came to this problem in a challenge.
There are two arrays A and B both of size of N and we need to return the count of pairs (A[i],B[j]) where gcd(A[i],B[j])==1
and A[i] != B[j]
.
I could only think of brute force approach which exceeded time limit for few test cases.
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]);
}
}
}
您能建议省时的算法来解决这个问题吗?
Can you advice time efficient algorithm to solve this.
无法共享问题链接,因为这是来自招聘方面的挑战.我记得添加了约束和输入/输出格式.
Not able to share question link as this was from a hiring challenge. Adding the constraints and input/output format as I remember.
输入-
- 第一行将包含N,即两个数组中存在的元素数.
- 第二行将包含N个以空格分隔的整数,即数组A的元素.
- 第三行将包含N个以空格分隔的整数,即数组B的元素.
输出-
- 根据条件对A [i],A [j]的计数.
约束-
- 1< = N< = 10 ^ 5
- 1<A [i],B [j] <= 10 ^ 9其中i,j<N
推荐答案
第一步是使用筛分以计算直至 sqrt(10 ^ 9)
的素数.然后,可以使用此筛子快速查找小于 10 ^ 9
的任意数量的所有素因数(请参见下面的代码示例中的 getPrimeFactors(...)
函数)
The first step is to use Eratosthenes sieve to calculate the prime numbers up to sqrt(10^9)
. This sieve can then be used to quickly find all prime factors of any number less than 10^9
(see the getPrimeFactors(...)
function in the code sample below).
接下来,对于每个素数为 p0,p1,...,pk
的 A [i]
,我们计算所有可能的子产品 X
- p0,p1,p0p1,p2,p0p2,p1p2,p0p1p2,p3,p0p3,...,p0p1p2 ... pk
并将它们计入地图 cntp [X]
.实际上,地图 cntp [X]
告诉我们元素 A [i]
可以被 X
整除的元素的数量,其中 X
是质数乘以0或1的幂的乘积.因此,例如对于数字 A [i] = 12
,质数因子是 2,3
.我们将计算 cntp [2] ++
, cntp [3] ++
和 cntp [6] ++
.
Next, for each A[i]
with prime factors p0, p1, ..., pk
, we compute all possible sub-products X
- p0, p1, p0p1, p2, p0p2, p1p2, p0p1p2, p3, p0p3, ..., p0p1p2...pk
and count them in map cntp[X]
. Effectively, the map cntp[X]
tells us the number of elements A[i]
divisible by X
, where X
is a product of prime numbers to the power of 0 or 1. So for example, for the number A[i] = 12
, the prime factors are 2, 3
. We will count cntp[2]++
, cntp[3]++
and cntp[6]++
.
最后,对于具有素数因子 p0,p1,...,pk
的每个 B [j]
,我们再次计算所有可能的子产品 X
并使用包含排除原则来计算全部非互素对 C_j
(即与[code> B [j] 共享至少一个素数的 A [i]
的数量).然后从对总数中减去数字 C_j
-N * N 以获得最终答案.
Finally, for each B[j]
with prime factors p0, p1, ..., pk
, we again compute all possible sub-products X
and use the Inclusion-exclusion principle to count all non-coprime pairs C_j
(i.e. the number of A[i]
s that share at least one prime factor with B[j]
). The numbers C_j
are then subtracted from the total number of pairs - N*N
to get the final answer.
注意:包含-排除"原理看起来像这样:
Note: the Inclusion-exclusion principle looks like this:
C_j = (cntp[p0] + cntp[p1] + ... + cntp[pk]) -
(cntp[p0p1] + cntp[p0p2] + ... + cntp[pk-1pk]) +
(cntp[p0p1p2] + cntp[p0p1p3] + ... + cntp[pk-2pk-1pk]) -
...
并说明了一个事实,即在 cntp [X]
和 cntp [Y]
中,我们可以算出相同的数字 A [i]
两次,因为它可以被 X
和 Y
整除.
and accounts for the fact that in cntp[X]
and cntp[Y]
we could have counted the same number A[i]
twice, given that it is divisible by both X
and Y
.
这是该算法的可能的C ++实现,其产生的结果与OP的朴素O(n ^ 2)算法相同:
Here is a possible C++ implementation of the algorithm, which produces the same results as the naive O(n^2) algorithm by OP:
// 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]的一些分析结果]
:
I cannot estimate the complexity analytically, but here are some profiling result on my laptop for different N
and uniformly random A[i]
and 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 comparison, the O(n^2) approach takes:
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
这篇关于小于O(n ^ 2)复杂度的两个数组的互质对数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!