0

Написал такой алгоритм, он выдает правильные результаты, но очень долго решает. В файле задаются 2 числа - a и b (a < b), нужно найти в этом промежутке(a - b) количество чисел не кратных 7, как ускорить этот алгоритм?

#include <iostream>
#include <fstream>
using namespace std;
int main() {

    int a = 0, b = 0, ans = 0;

    ifstream inp;
    ofstream otp;
    inp.open("input.txt");
    otp.open("output.txt");

    inp >> a >> b;
    for (; a <= b; a++) {
        if (a % 7 != 0) {
            ans++;
        }
    }

    otp << ans;

    return 1;
}
19
  • 4
    как ускорить этот алгоритм? Отказаться от тупого перебора, немножко подумать и вывести прямую формулу.
    – Akina
    24 ноя 2018 в 19:04
  • @Akina формулу для промежутка? 24 ноя 2018 в 19:24
  • 1
    Можно и для промежутка... но проще F(a,b) = F(1,b) - F(1,a-1).
    – Akina
    24 ноя 2018 в 19:27
  • @Akina не понимаю, что это за формула? F-? 24 ноя 2018 в 20:10
  • 1
    Не надо ничего перебирать... F(1,x) = x - x DIV 7.
    – Akina
    28 ноя 2018 в 16:57

1 ответ 1

2

Подразумевая a <= b:

  1. Выровняем значение a вверх к ближайшему кратному 7

    int a7 = (a + 7 - 1) / 7 * 7; // см. ниже о делении
    
  2. Выровняем значение b вниз к ближайшему кратному 7

    int b7 = b / 7 * 7; // см. ниже о делении
    
  3. Посчитаем количество чисел, кратных 7 в нашем диапазоне

    int k7 = a7 <= b7 ? (b7 - a7) / 7 + 1 : 0;
    
  4. Вычтем это значение из общего количества чисел в диапазоне

    int n7 = (b - a + 1) - k7;
    

    Это и есть ответ задачи.

Если значения a и b могут быть отрицательными, то в шагах 1 и 2 вместо языкового целочисленного деления / следует реализовать и использовать Евклидово деление

int euclidean_div(int a, int b)
{ // Для `b > 0`
  return a >= 0 ? a / b : (a - b + 1) / b;
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.