我怎样才能减少下面的代码块的时间复杂度？

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++;
    }
}

Answer 1

通过计算整除数的计数，将其添加到用b整除数的计数，与由LCM整除数的计数两次减去它的一个（最小公倍数），B。

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

因为计算最小公倍数你计算可以在O(log(min(a,b)))计算GCD（最大公约数）

注意：如果包括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;

Answer 2

在我看来，当你描述你的代码不起作用：它计算为每数量由b整除。您应该检查，如果我是a或b多

if (i % a == 0 && i % b != 0) {...
} else if (i % a != 0 && i % b == 0) {...
}

我也建议你采用不同的方法：找到a的倍数b直到你到达n并数着数。从和删除列表中的相同numers（更好，如果你做的最后一笔之前）

Answer 3

之前对其进行优化，以确保它工作第一。

现在，你要检查，如果一个号码是唯一的b或两者a和b整除。为了让a或b但不同时，你需要切换i % b==0第一条件i % b!=0：

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

你可以加快速度一件小事是应该做的可分性检查只是一次每个并保存结果而不是两次。然后，你可以使用一个XOR为最终结果。

for(int i = 1; i <= n; i++) {
    int div_a = (i % a == 0);
    int div_b = (i % b == 0);

    if (a ^ b) {
        count++;
    }
}

Answer 4

让我们先从这一点：

    temp = a;
    while(temp < n) {
        if(temp%b != 0) {
            count++;
        }
        temp += a;
    }
    temp = b;
    while(temp < n) {
        if(temp%a != 0) {
            count++;
        }
        temp += b;
    }

其次，考虑到一些骗子。如果a%b == 0然后任意数量由a整除也将是b整除;和类似的b%a == 0。在这两种情况下，计数为零。

如果a == 0则没有数是整除a;和类似的用于b == 0;如果两个a和b为零，则计数为零。

最后;不要忘了，（在C）x%0的行为是不确定的，你需要警惕这一点。

结合上述所有你喜欢的东西：

    if( (a == 0) && (b == 0) ) {
        return 0;
    }
    if( (a != 0) && (b != 0) ) {
        if( (a%b == 0) || (b%a == 0) ) {
            return 0;
        }
    }

    count = 0;
    if(a != 0) {
        temp = a;
        while(temp < n) {
            if(temp%b != 0) {
                count++;
            }
            temp += a;
        }
    }
    if(b != 0) {
        temp = b;
        while(temp < n) {
            if(temp%a != 0) {
                count++;
            }
            temp += b;
        }
    }
    return count;

下一轮秘籍：

• 如果n <= 1然后计数必须为零。
• 如果a == 1或a == -1那么所有的数字都是由a整除。
• 如果b == 1或b == -1那么所有的数字都是由b整除。

为了处理这些我会移动到“嵌套开关”，以尽量减少分行数目，如：

switch(a) {
    case 0:
        switch(b) {
            case 0:
                ...
                break;
            case -1:
            case 1:
                ...
                break;
            default:
                ...
                break;
        }
        break;
    case -1:
    case 1:
        switch(b) {
            case 0:
                ...
                break;
            case -1:
            case 1:
                ...
                break;
            default:
                ...
                break;
        }
        break;
    default:
        switch(b) {
            case 0:
                ...
                break;
            case -1:
            case 1:
                ...
                break;
            default:
                ...
                break;
        }
        break;
}