algorithm - 来自两个数组的互质数对的计数小于 O(n^2) 复杂度
问题描述
我在挑战中遇到了这个问题。有两个大小为 N 的数组 A 和 B,我们需要返回对 (A[i],B[j]) 的计数,其中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
解决方案
第一步是使用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]) -
...
并解释了这样一个事实,即cntp[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
推荐阅读
- javascript - 使用 Invisible Captcha V2 时何时调用 grecaptcha.execute()
- javascript - 使用 Object.assing 将全局对象与另一个对象组合,无法访问连接的对象?
- java - 从数组或 ArrayList 对象中随机选择。程序应该重复,直到用户准备好退出
- intellij-idea - IntelliJ 卡在加载页面
- r - R中具有%Y-%m-%d%H:%M时间序列格式的指数平滑预测
- arrays - Discord.JS Sharding Guild ID列表问题
- javascript - 我们可以使用提交表单将 id 发送到文件本身吗
- java - 为什么 Android Material Design 选项卡布局不起作用?
- android - 无法在我的项目中编写 SQlteAssethelper
- javascript - 使用 api 从 youtube 收集标题会在 jekyll 中产生奇怪的行为