Алгоритмы. алгоритмы (5). A. Количество нулей на интервале 2)

• Название: A. Количество нулей на интервале 2)
• Анкор: Алгоритмы
• Дата: 23.10.2022
• Размер: 34.28 Kb.
• Имя файла: алгоритмы (5).docx
• Тип: Документы; #750353

A. Количество нулей на интервале (0.2)

Ограничение времени	1 секунда
Ограничение памяти	32.0 Мб
Ввод	стандартный ввод
Вывод	стандартный вывод

Поступают запросы на вычисление количества нулей на некотором интервале заданного одномерного массива.

Реализуйте эффективную обработку большого числа таких запросов.

Формат ввода

В первой строке вводится одно натуральное число nn (1≤n≤107)(1≤n≤107) – количество чисел в массиве.

Во второй строке вводятся nn чисел от 00 до 99 – элементы массива.

В третьей строке вводится одно натуральное число kk (1≤k≤106)(1≤k≤106) – количество запросов на вычисление количества нулей.

В следующих kk строках вводится по два числа ll и rr через пробел – номера левого и правого элементов отрезка массива (1≤l≤r≤n)(1≤l≤r≤n). Считается, что элементы нумеруются с единицы.

Формат вывода

В одной строке – выведите через пробел количество нулей каждого запроса на соответствующем отрезке массива.

Система оценки

Группа	Баллы	Доп. ограничения		Необх. группы	Комментарий
		nn	kk
1	1	–	–		Тесты из условия.
2	1	n≤104n≤104	k≤104k≤104	1
3	2	n≤104n≤104	k≤105k≤105	1 – 2
4	2	n≤105n≤105	k≤105k≤105	1 – 3
5	2	n≤106n≤106	k≤105k≤105	1 – 4
6	2	n≤107n≤107	k≤106k≤106	1 – 5	Offline-проверка

Пример 1

5 0 9 5 2 2 10 3 3 3 4 2 5 2 4 3 4 1 5 3 5 2 4 1 3 3 5	0 0 0 0 0 1 0 0 1 0

Пример 2

5 8 8 8 2 4 10 1 5 2 3 3 4 2 3 3 5 1 5 3 5 2 4 2 4 3 4	0 0 0 0 0 0 0 0 0 0

Пример 3

5 5 1 7 7 8 10 2 3 2 4 2 4 3 3 3 3 3 4 3 3 3 5 1 4 1 3	0 0 0 0 0 0 0 0 0 0

Пример 4

5 7 8 2 6 5 10 1 4 2 4 3 3 1 3 3 5 2 3 3 4 1 5 2 4 3 3

B. НОД и простые числа (0.2)

Ограничение времени	1 секунда
Ограничение памяти	64.0 Мб
Ввод	стандартный ввод
Вывод	стандартный вывод

Борис проходит отбор на стажировку в Яндекс, и в одном из заданий ему встречаются сразу две темы - наибольший общий делитель (НОД) и простые числа.

Определение: наибольшим общим делителем двух целых положительных чисел AA и BB называют такое число GG, что:

1. 
   AA делится на GG нацело (GG является делителем AA);
   
2. 
   BB делится на GG нацело (GG является делителем BB);
   
3. 
   не существует числа HH такого, что GG < HH и HH удовлетворяет условиям 1 и 2.
   

Определение: число PP называется простым, если у него есть ровно два различных делителя: 1 и само число PP.

К примеру:

• 
  число 1 не является простым, так как у него только один делитель — 1;
  
• 
  4 не простое, так как у 4 есть три делителя — 1, 2, 4;
  
• 
  6 не простое, так как у 6 четыре различных делителя — 1, 2, 3, 6.
  

В качестве задания Борису необходимо решить следующую задачу:

«Даны два целых положительных числа AA и BB, можно ровно один раз умножить либо AA, либо BB на любое простое число. Какого наибольшего значения НОД можно добиться с помощью такого умножения?»

Пример:

• 
  Пусть AA = 20, BB = 45. НОД(20, 45) = 5.
  
• 
  При умножении числа AA на простое число 3 итоговый НОД(20 ⋅ 3, 45) = 15.
  
• 
  При умножении числа BB на простое число 2 итоговый НОД(20, 45 ⋅ 2) = 10.
  

Помогите Борису попасть в Яндекс.

Формат ввода

В первой строке дано два целых положительных числа AA и BB (1≤A(1≤A, B≤1012)B≤1012).

Формат вывода

Выведите единственное целое число – наибольшее значение НОД, которого можно добиться умножением одного из чисел AA и BB на простое число.

Система оценки

Группа	Баллы	Доп. ограничения	Необх. группы	Комментарий
		A,BA,B
1	1	–		Тесты из условия.
2	1	1≤A,B≤1001≤A,B≤100	1
3	1	1≤A,B≤1041≤A,B≤104	1 – 2
4	2	1≤A,B≤1061≤A,B≤106	1 – 3
5	2	1≤A,B≤1091≤A,B≤109	1 – 3
6	3	1≤A,B≤10121≤A,B≤1012	1 – 4	Offline-группа

Пример 1

7 1	7

Пример 2

12 54	18

Пример 3

20 45	15

Примечания

Рассмотрим детально пример входных данных:

1. 
   Необходимо умножить число BB = 1 на простое число 7, тогда НОД(7, 1 ⋅ 7) = 7.
   
2. 
   НОД(12, 54) = 6. Для получения оптимального ответа необходимо умножить число AA = 12 на простое число 3.
   В таком случае НОД(12 ⋅ 3, 54) = НОД(36, 54) = 18, так как 54 = 18 ⋅ 3 и 36 = 18 ⋅ 2.
   

• 
  Другой разрешенный, но неоптимальный вариант — умножить BB = 54
  на простое число 2.
  В таком случае итоговый НОД(12, 54 ⋅ 2) = НОД(12, 108) = 12,
  так как 108 = 12 ⋅ 9.
  
• 
  Неразрешенный, пусть и более оптимальный вариант — умножить AA = 12
  на не простое число 9.
  В таком случае НОД(12 ⋅ 9, 54) = НОД(108, 54) = 54 > 18.
  Но так как 9 не является простым числом, такое умножение по условию задания делать нельзя.
  

С. Теорема Лагранжа (0.2)

Ограничение времени	0.5 секунд
Ограничение памяти	32.0 Мб
Ввод	стандартный ввод
Вывод	стандартный вывод

Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы четырех точных квадратов. По данному числу nn найдите такое представление: напечатайте от 1 до 4 натуральных чисел, квадраты которых дают в сумме данное число.

Формат ввода

Программа получает на вход одно натуральное число nn (0≤n≤2⋅109)(0≤n≤2⋅109).

Формат вывода

Программа должна вывести от 1 до 4 натуральных чисел через пробел, квадраты которых дают в сумме данное число.

Группа	Баллы	Доп. ограничения	Необх. группы	Комментарий
		nn
1	1	–		Тесты из условия.
2	1	n≤10n≤10	1
3	1	n≤103n≤103	1 – 2
4	1	n≤104n≤104	1 – 3
5	2	n≤106n≤106	1 – 4
6	2	n≤108n≤108	1 – 5
7	1	n≤109n≤109	1 – 6	Offline-группа
8	1	n≤2⋅109n≤2⋅109	1 – 7	Offline-группа

Пример 1

1	1

Пример 2

2	1 1

Пример 3

3	1 1 1

Пример 4

0	0