1) Факторизация факториала
Сперва решетом находим все простые числа от 1 до N. Понятно, что все эти числа и есть делители N!,
потому что N! = 1 * 2 * ... * N.
И записываем простые числа в массив p[].
То есть он будет выглядеть так: p[1] = 2, p[2] = 3, p[3] = 5, ...
Требуется посчитать, с какой степенью простой делитель p входит в число N!,
т.е. найти наибольшее x такое, что N! делится на px.
Теперь как надо искать x для p?
Конечно, не до бесконечности, потому что берем только целую часть.
Сложность нахождения степени делителя факториала O(logpN)
Итоговая сложность ≈ O(NlogN), если считать грубо.
2) Реккурентное соотношение
Если посмотреть на ограничения, N ≤ 1018, то легко понять, что можно решать эту задачу за O(1) или за O(logN).
- Можно воспользоваться быстрым возведением матрицы в N-ую степень за O(logN).
- Можно найти перебором начальные несколько значений функции, затем найти закономерность(период функции). Скажем период равен P. И просто найти ответ за O(1), т.е. взять N по модулю P и вывести последнюю цифру, т.е. взяв f(N%P) по модулю 10.
3) Постройки
Надо найти количество построений дорог между N центрами, где N ≤ 100.
Можно представить сеть центров, как ориентированный граф с N вершинами.
Максимум дорог(неориентированных) между вершинами такого графа может быть 
.
.И у каждой дороги(u - v) будет три состояния:
- u → v.
- v → u.
- дорог между u и v вообще нет.
То есть ответ: 
. Так как ответ может быть большим, надо использовать длинную арифметику.
. Так как ответ может быть большим, надо использовать длинную арифметику.4) Фея
Надо найти количество таких заполнений бланков ответа из N вопросов по K ответов, чтобы ни в одном варианте заполнения не было ни одного правильного ответа.
Нам дано какое-то множество правильных ответов к каждому вопросу, и мы можем выбрать любой
вариант ответа, кроме правильного. Т.е., если есть K ответов, то один из них правильный, а остальные K - 1 неправильные. Всего вопросов N и мы можем выбрать любые K - 1 неправильных ответов. Значит ответ: (K - 1)N. Здесь также нужно воспользоваться длинной арифметикой.
5) Райхан и таблица Менделеева
В данной задаче надо быстро проверять, находиться ли в таблице Менделеева элемент si + si + 1(конкатенация двух символов строки s).
- Для этого в C++, можно воспользоваться map'ом. Сложность будет O(NlogM)
- Так же можно завести буленовый массив 26x26(в паскале можно сделать array['a'..'z', 'a'..'z'] of boolean). И для каждого элемента хранить true, если он есть в таблице Менделеева, иначе false. Или можно просто хранить элементы в хэш-таблице. Тут ограничения не большие и методов много. То есть сложность при таких методах будет O(N)
6) Веревка
Сперва надо отсортировать все окружности по углу(угловая сортировка). Можно было сортировать по тангенсу угла. Дальше надо было придумать формулу для нахождения длины части веревки соединяющей две последовательные окружности. Точную формулу можете вывести сами, для этого нужно знать, как вычислять расстояние между двумя точками в декартовой системе координат, и знать теорему косинусов.
Сложность будет O(NlogN).
7) Палиндромы
Ограничения в этой задаче N ≤ 102000.
Пусть длина N равна n.
Для длины k, количество палиндромов будет 10[k / 2], где [x] = округленное значение x. Надо сложить все значения для k = 1..n - 1.
Для длины k, количество палиндромов будет 10[k / 2], где [x] = округленное значение x. Надо сложить все значения для k = 1..n - 1.
Теперь рассмотрим палиндромы длины n. Будем считать количество палиндромов так.
если N = abc...xyz, то прибавляем к ответу:
если N = abc...xyz, то прибавляем к ответу:
(a - 1) * 9 * 9 * ... * 9 (до середины, так как это палиндром)
a * (b - 1) * 9 * ... * 9 (так же до середины)
... И так далее.
Cложность будет примерно O(n2).
Comments (0)
