Как я могу уменьшить временную сложность следующего блока кода?

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

Давайте начнем с этого:

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

Answer 2

Мне кажется, что ваш код не работает так, как вы его описываете: он учитывается для каждого числа, кратного b.Вы должны проверить, является ли я кратным a или b

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

. Я также предлагаю вам другой подход: найдите кратные значения a и b, пока не достигнете n, и посчитайте эти числа.убрать те же цифры в списках из суммы (лучше, если вы сделаете это до окончательной суммы)

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

Рассчитайте количество чисел, кратных a, добавьте его к числу чисел, кратных b, вычтите его с удвоенным числом чисел, делимых на lcm (наименьшее общее кратное) a, b.

Сложность времени: 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;