Задача "Светофоры" с codeforces. Код слишком медленный

@Tikoo123 · Регистрация: 09.10.2023

Студворк — интернет-сервис помощи студентам

Выходит ошибка на 9 тесте, указывающая что программа слишком медленная. Как ускорить код?
Сама задача - https://codeforces.com/gym/102386/problem/H

H. Светофоры
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Валя учится в школе в четвёртом классе. Все эти годы он составлял оптимальный маршрут от дома до здания школы. Эту задачу осложняет то, что время ходьбы по одному и тому же маршруту не всегда одинаковое: оно зависит от того, как долго придётся стоять на светофорах. Чтобы не стоять слишком долго, выгодно переходить на перекрёстках, где зелёный свет горит то в одном, то в другом направлении. Стоя на таком перекрёстке Валя и придумал эту задачу.

Представьте, что вы стоите на перекрёстке, и в обе стороны горит красный свет. На всех светофорах стоит счётчик, показывающий, сколько секунд осталось ждать. В одну сторону счётчик показывает A
секунд, в другую — B секунд. Каждую секунду числа на обоих счётчиках одновременно уменьшаются на 1

. Как только один из счётчиков достигнет нуля, загорится зелёный свет.

Пока ещё горит красный, интересны все такие моменты, когда числа на счётчиках будут различаться в целое число раз, то есть когда их частное — целое число. Посчитайте, сколько раз такое случится.
Входные данные

В единственной строке через пробел вводятся целые числа A
и B — числа на первом и втором счётчиках соответственно (1≤A,B≤109

).
Выходные данные

В единственной строке выведите одно целое число — количество раз, когда числа на счётчиках будут различаться в целое число раз до того, как один из них достигнет нуля.

Мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cmath>
 
 
using namespace std;
 
 
int main() {
 
 
    int a, b;
    cin >> a >> b;
    int c = 0;
    int Min = min(a, b);
    int Max = max(a, b);
    if (a == b) 
    {
        cout << a;
    }
    else 
    {
        while (Min > 0)
        {
            if (Max % Min == 0)
            {
                c++;
            }
            Max--;
            Min--;
        }
        cout << c;
    }
    
 
    
}

@TheCalligrapher · 10.10.2023, 05:31

Сообщение от Tikoo123

Как ускорить код?

Никак. Код выкинуть целиком. Зачем же вы взялись буквально симулировать поведение светофоров? Вы бы еще 1 секунду задержки на каждой итерации добавили, чтобы "совсем как в жизни" получилось...

---

Пусть исходные значения на счетчиках равны a и b (a >= b). И пусть d = a - b. По мере того, как счетчики убывают, разность между ними постоянна и равна d.

В моменты, когда текущее значение а делится на текущее значение b, будет выполняться a = bk для некоего k. То есть в каждый такой момент d = bk - b = b(k-1). То есть каждому делителю d (не превышающему исходное b) соответствует какая-то комбинация делящихся друг на друга счетчиков.

Таким образом, ответ задачи: количество делителей d, не превышающих b. А чтобы найти их, я думаю, обычный перебор до корня из d будет достаточно быстрым.

@KSergey9 · 10.10.2023, 09:04

Сообщение от TheCalligrapher

обычный перебор до корня из d будет достаточно быстрым.

До корня - наверное будет лишним.
(например, при входных данных 50 и 40 ответ 4, а это больше корня из разницы. (хотя, возможно, вопрос в том куда округлить?)

Добавлено через 1 минуту

Не по теме:

Сообщение от Tikoo123

1≤A,B≤109

Я так понимаю, что это как всегда 10 в 9 степени?
К чему тогда всё это дурное словоблудие, спросить бы у авторов. 10 в 9-й секунд на светофоре, ага.
Пейсатели, my ass

@TheCalligrapher · 10.10.2023, 09:07

Сообщение от KSergey9

До корня - наверное будет лишним.

Если искать делители перебором, то перебор, разумеется, имеет смысл делать до минимума из корня и b. Но это уже не принципиально. Можно просто до корня.

Сообщение от KSergey9

(например, при входных данных 50 и 40 ответ 4, а это больше корня из разницы.

Не понял этого замечания.

При входных данных 50 и 40 разница равна 10. То есть перебор до корня из 10 проверит три числа (1, 2, 3), обнаружит две пары делителей (1, 10) и (2, 5) и засчитает все четыре делителя, ибо все они меньше 40. Ответ - 4.

@KSergey9 · 10.10.2023, 09:15

Сообщение от TheCalligrapher

обнаружит две пары делителей (1, 10) и (2, 5) и засчитает все четыре делителя

При стартовых 40 и 50 возникнет 4 пары, делящихся друг на друга нацело:
(20, 10)
(15, 5)
(12, 2)
(11, 1)

поэтому я не могу сообразить о каких засчитанных делителях вы говорите.

@TheCalligrapher · 10.10.2023, 09:35

Сообщение от KSergey9

При стартовых 40 и 50 возникнет 4 пары делящихся друг на друга нацело:
(20, 10)
(15, 5)
(12, 2)
(11, 1)

Совершенно верно.

Как я сказал выше, нам нужно найти все делители разницы, то есть все делители 10 (= 50-40).
Эти делители и будут определять наши пары. (Второе число в паре равно найденному делителю +10).

Делители 10 мы найдем перебором кандидатов от 1 до 3. Помним, что каждый кандидат может дать нам два делителя. В результате мы найдем делители 1, 10, 2, 5. Все они меньше 40.

То есть мы получаем именно ваши пары, приведенные вами выше, четыре штуки: (1, 11) (10, 20) (2, 12) (5, 15),

Сообщение от KSergey9

я не могу сообразить о каких засчитанных делителях вы говорите.

"Засчитанные" - значит меньше или равно 40. Когда мы ищем делители, мы должны отбросить все, которые больше 40.

P.S. Если бы нам не нужно было отсеивать делители по этому критерию, то есть интересовали бы все делители, я бы посоветовал вычислять количество делителей через факторизацию. Это эффективнее. Но для данной задачи притягивать сюда за уши факторизацию не нужно. Она и обычным перебором до корня уложится в отведенное время.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .