eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Теорема Ферма

Теорема Ферма

Ліміт часу 0.5 секунд
Ліміт використання пам'яті 64 MiB

...усe вже придумано у далекі средні віки — і сучасними авторами лише крадеться. А средньовічні автори, у свою чергу, вкрали ці думки у античних, і якщо щось нове у них промайнуло — це, значить, з джерел, які не збереглись і до нас не дійшли.

І. Губерман

Напевно немає жодної людини у світі, яка б нічого не чула про велику теорему Ферма. Вона має унікальну історію, яку не має напевно жодна теорема у світі, над нею бились кращі розуми планети протягом 350 років, поки вона не була доведена американським математиком Ендрю Уайлсом. Формулювання теореми надзвичайно просте: для довільного натурального числа k > 2 рівняння

x^k + y^k = z^k

не має натуральних розв'язків a, b та c. Якщо бути точним, Ферма написав на полях книги Діофанта “Арифметика”: "Не можна розкласти ні куб на два куби, ні квадрато-квадрат (тобто четверту степінь числа) на два квадрато-квадрати, ні взагалі ніякий степінь вище квадрату і до нескінченності не можна розкласти на два степені з тим же показником. Я відкрив цьому воістину прекрасне доведення, але ці поля для нього замалі". У цій задачі Вам, звичайно, не прийдеться доводити цю теорему, необхідно лише за заданим натуральним числом n визначити, скількома способами його можна подати у вигляді суми двох степенів натуральних чисел з показником k. Інакше кажучи, скільки існує невпорядкованих пар натуральних чисел (x, y), які задовільняють рівнянню:

x^k + y^k = n

Вхідні дані

У вхідному файлі міститься пара чисел n, k (1n10^18, 1k100).

Вихідні дані

Виведіть єдине число – кількість розв'язків рівняння.

Приклад

Вхідні дані #1
10 2
Вихідні дані #1
1
Автор Євген Служаєв