Третій тур – 2012

скачати файл завдання (*.doc)

Розв'язки задач відправляти з 26.11.2012р. по 2.12.2012 р.

Розв'язок задачі відправляти як вкладений текстовий файл з іменем завдання.

1. Магічні числа (20 балів)

Ім'я вхідного файлу: magicnum.dat

Ім'я вихідного файлу: magicnum.ans

Програма: magicnum.*

Обмеження часу: 6с

Обмеження пам'яті: 64 мбайт

Гаррі Поттер на дозвіллі займається дослідженням властивостей чисел. Одного разу в старому заклинанні він побачив число 164295863084308762162943510238 і захотів дізнатися, а чи ділиться воно на 3? Після того, як Гаррі вирішив свою задачу, шкідлива Герміона вирішила дізнатися, а чи ділиться це число на 11? Тільки-тільки Гаррі Поттер розібрався із завданнями Герміони, як прийшов Рон Уізлі і задав нове завдання, чи ділиться це число на 13?

Щоб назавжди позбавитися від питань друзів про ділення чисел, Гаррі захотів вирішити загальну проблему. Визначити чи ділиться число N (0<N<10^¹⁰⁰⁰) на m(0<m<100).

Формат вхідних даних :

У першому рядку вхідного файлу записано ціле число m. У другому рядку записано число N.

Формат вихідних даних :

У вихідний файл вивести слово "YES", якщо число N ділиться на m, або залишок від ділення N на m.

Розв'язок задачі відправляти як вкладений текстовий файл з іменем завдання.

2. Магічні суми (100 балів)

Ім'я вхідного файлу:  simsum.dat

Ім'я вихідного файлу: simsum.ans

Програма: simsum.*

Обмеження часу: 6с

Обмеження пам'яті: 64 мбайт

Гаррі Поттер  вивчаючи прості числа, мав взнати, що будь-яке ціле число більше 1 можна єдиним способом представити у вигляді добутку простих множників. Але при вивченні арифметики разом із Роном Уізлі, вони замість добутку вирішили представляти цілі числа у вигляді суми простих доданків (в не спадаючому порядку), і виявили, декілька таких сум. Так для числа 13 є 9 таких сум: 13=13, 13=2+2+2+2+2+3, 13=2+2+3+3+3, 13=2+3+3+5, 13=2+2+2+2+5, 13=3+5+5, 13=2+2+2+7, 13=3+3+7, 13=2+11.

Допоможіть друзям визначити кількість сум для будь-якого числа.

Формат вхідних даних :

Вхідний файл містить одне ціле число N (1<N≤5000).

Формат вихідних даних :

У вихідний файл вивести кількість сум.