Задача Один из двух

@semen1984 · Регистрация: 07.05.2024

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

Даны n,m и k. Выведите k-е наименьшее натуральное число, которое делится ровно на одно из чисел n и m.
Формат входных данных
Даны три целых числа n,m и k (1≤n≠m≤10^8, 1≤k≤10^10).

Формат результата
Выведите одно число — ответ на задачу.

Примеры
Входные данные
2 3 5
Результат работы
9
Входные данные
1 2 3
Результат работы
5

Есть понимание, что нужно использовать НОД, НОК, но нет идей как именно.
"Долгое" решение, которое не использует НОД, НОК и не проходит тесты:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def nod(a, b):
    while b:
        a, b = b, a % b
    return a
 
def nok(a, b):
    return (a/nod(a,b))*b
 
n, m, k = map(int, input().split(' '))
i = 0
kolvo = 0
while kolvo != k:
    i += 1
    if (i%n == 0 and i%m != 0) or (i%n != 0 and i%m == 0):
        kolvo += 1
        #print('podoshlo=',i)
print(i)

@Aael · 30.07.2024, 11:37

semen1984, подобрать половинным делением? * lcm не пересчитывать, рекурсию в цикл, проверить существование решения

Python
1
2
3
4
5
6
7
8
9
10
11
from math import lcm
 
def f(a, b, n, m, k):
    if a == b: return a
    x, s = (a + b) // 2, 0
    s += x // n - x // lcm(n, m) # сколько из [1,x] делятся на n но не на m
    s += x // m - x // lcm(n, m) # сколько из [1,x] делятся на m но не на n
    return f(x + 1, b, n, m, k) if s < k else f(a, x, n, m, k)
 
for k in range(1, 10):
    print(k, '->', f(1, 10**10, n=4, m=6, k=k))

@semen1984 · 30.07.2024, 12:56 **[ТС]**

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

semen1984, подобрать половинным делением? * lcm не пересчитывать, рекурсию в цикл, проверить существование решения

интересное решение через бинарный поиск и рекурсию
с виду кажется, что всё правильно, но на том же "длительном" тесте выдаёт "неправильный ответ", моё решение не проходит по ограничению машинного времени
к сожалению, никакой отладочной информации и тестовых сценариев система проверки не выдаёт

@Aael · 30.07.2024, 13:17

semen1984, думаю, нужно отрезок поиска увеличить, хотябы до 10**20 (или больше сколько там глубины рекурсии хватит, 10**100? )

@udmurt2024 · 30.07.2024, 13:31

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#n, m, k = 2,3,5
n, m, k = map(int, input().split(' '))
if n>m: n,m=m,n
ni,mi=n,m
nn=0
while nn<k:
    if ni<mi:
        nn+=1
        nm=ni
        ni+=n
    elif mi<ni:
        nn+=1
        nm=mi
        mi+=m
    else:
        ni+=n
        mi+=m
print(nm)

@semen1984 · 30.07.2024, 14:24 **[ТС]**

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

semen1984, думаю, нужно отрезок поиска увеличить, хотябы до 10**20 (или больше сколько там глубины рекурсии хватит, 10**100? )

на 10**20 все тесты отработали, спасибо!!!

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

PythonВыделить код
#n, m, k = 2,3,5
n, m, k = map(int, input().split(' '))
if n>m: n,m=m,n
ni,mi=n,m
nn=0
while nn<k:
if ni<mi:
nn+=1
nm=ni
ni+=n
elif mi<ni:
nn+=1
nm=mi
mi+=m
else:
ni+=n
mi+=m
print(nm)

спасибо за решение, но оно, как и моё, валится по ограничению на машинное время

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@Aael 964 / 485 / 241 Регистрация: 02.06.2016 Сообщений: 760
	30.07.2024, 13:17
	semen1984, думаю, нужно отрезок поиска увеличить, хотябы до 1020 (или больше сколько там глубины рекурсии хватит, 10100? ) 0

Задача Один из двух

Решение