Идеальная пара чисел

@MY4A · Регистрация: 18.12.2021

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

(Не)достижимый идеал
Недавно Софья Ковалевская прочла про понятие «идеальной пары» целых чисел. Пара целых чисел a и b называется идеальной, если gcd(a,b)=min(a,b) где gcd — наибольший общий делитель двух целых чисел.
Теперь Софья не может уснуть, пока не узнает количество чисел из полуинтервала [l, r), образующих идеальную пару с числом n. Помогите ей обрести покой на ближайшую ночь.
Формат входных данных
В первой строке записано одно целое число t(1 ≤t ≤ 10^4) — количество ночей, в которые Софья не может уснуть. Далее следуют t наборов входных данных.
Каждый набор входных данных состоит из одной строки, содержащей три целых числа n, l, r (1≤n≤l<r≤10^18) — число, для которого необходимо найти количество идеальных пар, и границы полуинтервала соответственно.
Формат результата
Для каждого набора входных данных в отдельной строке выведите искомое число — количество чисел, n
идеальную пару в данном полуинтервале [l,r).
Примеры
4
1 2 3
5 5 15
2 2 3
1 1 1000000000000000000
Результат работы
1
2
1
999999999999999999
В первом примере
gcd(1,2)=min(1,2)=1. Других чисел в полуинтервале нет, поэтому ответ равен 1.

Во втором примере
gcd(5,5)=min(5,5)=5, gcd(5,10)=min(5,10)=5. Несмотря на то, что число 15 подходит числу 5, оно не входит в полуинтервал [5,15)и, следовательно, в ответе не учитывается.

@eaa · 18.12.2021, 20:42

на перебор:

Python
1
2
3
4
5
6
7
8
9
from math import gcd
 
for _ in range(int(input())):
    n, left, right = map(int, input().split())
    count = 0
    for i in range(left, right):
        if gcd(n, i) == min(n, i):
            count += 1
    print(count)

ускоряй, по времени все равно не пройдет.

Не по теме:

хоть одна более менее нормальная задача за день тут...

@MY4A · 18.12.2021, 21:00 **[ТС]**

Спасибо большое, не подскажешь как можно ускорить?(или на другом языке написать)

@eaa · 18.12.2021, 21:08

MY4A, язык роли не сыграет.

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

1≤n≤l<r≤10^18

первое ускорение

Python
1
if gcd(n, i) == n

а от сюда уже вычисляется формула и убирается внутренний цикл

@rembor · 19.12.2021, 09:25

eaa, а что за формула то?

@eaa · 19.12.2021, 09:46

rembor, её нужно вывести. пробуй самостоятельно. если не получится, скидывай попытки сюда.

@rembor · 19.12.2021, 09:57

eaa, (r - l) / n?

@eaa · 19.12.2021, 10:01

rembor, нет. но направление правильное.

@rembor · 19.12.2021, 11:45

eaa, (r - l) / n + (r - l) % n?

Добавлено через 23 минуты
eaa, или что...

Добавлено через 53 минуты
eaa, не проходит

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@MY4A 0 / 0 / 0 Регистрация: 18.12.2021 Сообщений: 2

	Идеальная пара чисел 18.12.2021, 20:21. Показов 2360. Ответов 8 Метки нет (Все метки) (Не)достижимый идеал Недавно Софья Ковалевская прочла про понятие «идеальной пары» целых чисел. Пара целых чисел a и b называется идеальной, если gcd(a,b)=min(a,b) где gcd — наибольший общий делитель двух целых чисел. Теперь Софья не может уснуть, пока не узнает количество чисел из полуинтервала [l, r), образующих идеальную пару с числом n. Помогите ей обрести покой на ближайшую ночь. Формат входных данных В первой строке записано одно целое число t(1 ≤t ≤ 10^4) — количество ночей, в которые Софья не может уснуть. Далее следуют t наборов входных данных. Каждый набор входных данных состоит из одной строки, содержащей три целых числа n, l, r (1≤n≤l<r≤10^18) — число, для которого необходимо найти количество идеальных пар, и границы полуинтервала соответственно. Формат результата Для каждого набора входных данных в отдельной строке выведите искомое число — количество чисел, n идеальную пару в данном полуинтервале [l,r). Примеры 4 1 2 3 5 5 15 2 2 3 1 1 1000000000000000000 Результат работы 1 2 1 999999999999999999 В первом примере gcd(1,2)=min(1,2)=1. Других чисел в полуинтервале нет, поэтому ответ равен 1. Во втором примере gcd(5,5)=min(5,5)=5, gcd(5,10)=min(5,10)=5. Несмотря на то, что число 15 подходит числу 5, оно не входит в полуинтервал [5,15)и, следовательно, в ответе не учитывается. 0

@MY4A 0 / 0 / 0 Регистрация: 18.12.2021 Сообщений: 2
	18.12.2021, 21:00 [ТС]
	Спасибо большое, не подскажешь как можно ускорить?(или на другом языке написать) 0

@rembor 0 / 0 / 0 Регистрация: 01.04.2020 Сообщений: 36
	19.12.2021, 09:25
	eaa, а что за формула то? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	19.12.2021, 09:46
	rembor, её нужно вывести. пробуй самостоятельно. если не получится, скидывай попытки сюда. 0

@rembor 0 / 0 / 0 Регистрация: 01.04.2020 Сообщений: 36
	19.12.2021, 09:57
	eaa, (r - l) / n? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	19.12.2021, 10:01
	rembor, нет. но направление правильное. 0

@rembor 0 / 0 / 0 Регистрация: 01.04.2020 Сообщений: 36
	19.12.2021, 11:45
	eaa, (r - l) / n + (r - l) % n? Добавлено через 23 минуты eaa, или что... Добавлено через 53 минуты eaa, не проходит 0

Идеальная пара чисел

Решение