c++ - 如何降低以下代码块的时间复杂度？

Question

我正在取 1 到 n 位数字并找到可被 a 或 b 整除但不能被两者整除的数字计数。我想通过一些逻辑变化来降低这个块的时间复杂度。

cin >> n >> a >> b >> k;      
for(int i = 1; i <= n; i++) {
    if(i % a == 0 && i % b==0) {
        count++;
    } else if(i % b == 0 && i % a != 0) {
        count++;
    }
}

标签： c++algorithmif-statementtime-complexity

Answer 1

计算可被 a 整除的数，将其与可被 b 整除的数相加，再减去可被 a、b 的 lcm（最小公倍数）整除的数的两倍。

时间复杂度：O(log(min(a,b)))

因为要计算最小公倍数，您需要计算 gcd（最大公约数），可以在O(log(min(a,b)))

注意：如果包含bits/stdc++.h，则可以使用内置函数计算 gcd： __gcd (int , int )

int lcm(int a, int b) {
        return (a * b)/__gcd(a,b);
    }

cin>>n>>a>>b>>k;

int divisible_by_a = n / a;
int divisible_by_b = n / b;
int divisible_by_both = n / lcm(a,b);

ans = divisible_by_a + divisible_by_b - 2*divisible_by_both;