Olymp8

Мат-мех 2015

11

Мат-мех 2015

12

Мат-мех 2015

13

Мат-мех 2015

14

Мат-мех 2015

15

Мат-мех 2015

16

Заполни массив 2

(делимость, динамическое программирование)

Требуется заполнить N элементов массива, пронумерованных числами от 1 до N (A[1]…A[N]), натуральными числами от 2 до N+1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A[i] делилось бы на i).

Напишите программу, которая для заданного N вычислит количество способов такого заполнения массива.

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

Вводится одно натуральное число N (1≤N≤60000).

Выходные данные Выведите одно число — искомое

количество способов заполнения массива

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

2

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

1

Комментарии Массив можно заполнить

единственным способом: 3 2

Мат-мех 2015

17

Заполни массив 1

Та же задача, но требуется привести пример хотя бы одной расстановки чисел 2,3,…, n+1 в массиве a[1..n] так, чтобы a[i] делилось на i

Вот один из вариантов:

a[i] = n+1 при i = 1 a[i] = i для остальных i

Мат-мех 2015

18

А теперь «Заполни массив 2»

Назовём расстановку из предыдущей задачи тривиальной

Решим динамическим программированием

Пусть dp[n] – ответ для n

dp[n] = SUM(dp[k])

по всем k, на которые делится n+1

dp[1] = 1, остальные вычисляем, перебирая для каждого i все его делители (которых не более 2sqrt(i))

За O(n*sqrt(n))

А при грамотном переборе и за О(n*logn)

Мат-мех 2015

19

Псевдопростые числа

Пусть a1 = 2, a2 = 3, an = a1∙a2∙...∙an-1 – 1 при n ≥ 3. Назовем числа ai псевдопростыми. Для заданного натурального числа X нужно ответить на вопрос: можно ли X однозначно представить в виде произведения псевдопростых чисел (представления, отличающиеся только порядком множителей, считаются одинаковыми), и, если можно — выдать разложение.

	Входные данные
	6
Входные данные	Выходные данные
Вводится одно натуральное число X, 1 < X ≤
	2 3
10^9.
	--------------------------------------------
	Входные данные
Выходные данные	5
Выведите псевдопростые числа,	Выходные данные
произведение которых равно X, в
	5
произвольном порядке. Если разложения не	--------------------------------------------
существует или оно не единственно, выдать 0.	Входные данные
	7
Мат-мех 2015	Выходные данные	20
	0