Simulare Lot 2009 Baraj 3 Juniori | multiplu

This was the problem page during the contest. Access the current page here.
Time limit: 0.03s Memory limit: 4MB Input: multiplu.in Output: multiplu.out

Se consideră două numere naturale nenule NN şi KK. Numim KK-şir un şir de numere naturale cu KK termeni.

Cerinţă

Determinaţi numărul format din ultimele 44 cifre ale numărului de KK-şiruri distincte cu proprietatea că fiecare dintre ele are cel mai mic multiplu comun al termenilor egal cu NN.

Date de intrare

Fişierul de intrare multiplu.in conţine pe prima linie cele două numere NN şi KK separate printr-un singur spaţiu.

Date de ieșire

Fişierul de ieşire multiplu.out conţine un singur număr natural reprezentând rezultatul cerut.

Restricții și precizări

  • 1N,K1091 \leq N, K \leq 10^9;

Exemplu

multiplu.in

5 2

multiplu.out

3

Explicație

Cele 3 23 \ 2 - şiruri cu cel mai mic multiplu comun al termenilor egal cu 55 sunt: (1,51, 5), (5,15, 1) şi (5,55, 5)

Log in or sign up to be able to send submissions!