Fişierul intrare/ieşire:marc.in, marc.outSursăOlimpiada pe Sector 2011, Clasa a 10-a
AutorCarmen Minca, Doina DrutaAdăugată deteodor94Teodor Plop teodor94
Timp execuţie pe test0.35 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Marc

Fie n şi k două numere naturale nenule, k < n. Numerele de la 1 la n se aşează, în ordine crescătoare, unul lângă altul, în sensul acelor de ceasornic, pe un cerc, numărul n ajungând să fie situat lângă numărul 1. Începând cu numărul 1, se marchează numerele din k în k, în direcţia: 1, 1+k, 1+2*k, 1+3*k, …. Marcarea încetează în momentul în care se marchează un număr pentru a doua oară. Denumim acest tip de marcare ca fiind marcare cu pasul k.

Cerinţă

Scrieţi un program care să citească numerele naturale nenule n şi k şi care să determine numărul m de numere dintre cele n care au rămas nemarcate şi numărul p de numere naturale x din intervalul [2, n] pentru care în urma marcării cu pasul x se obţin câte m numere nemarcate. 

Date de intrare

Fişierul de intrare marc.in conţine o singură linie pe care sunt scrise două numere naturale nenule n şi k, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire marc.out va conţine o două linii. Pe prima linie se va scrie numărul natural m reprezentând numărul de numere dintre cele n care au rămas nemarcate. Pe a doua linie a fişierului se va scrie numărul natural p reprezentând numărul de numere naturale x din intervalul [2, n] pentru care în urma marcării cu pasul x se obţin câte m numere nemarcate.

Restricţii

  • n şi k sunt numere naturale
  • 30 ≤ n ≤ 725000
  • 5 ≤ k ≤ 2400, k < n

Exemplu

marc.inmarc.outExplicatie
30 8
15
8
n=30 şi k=8. Se aşează pe cerc numerele de la 1 la 30. Începem marcarea cu numărul 1.
Se marchează în această ordine numerele: 1, 9, 17, 25, 3, 11, 19, 27, 5, 13, 21, 29, 7, 15, 23, 1.
Deoarece numărul 1 a fost marcat pentru a doua oară, marcarea numerelor încetează.
Pe cerc, au mai rămas m=15 numere nemarcate.
Numărul 15 se va scrie pe prima linie a fişierului marc.out.
În intervalul [2, 30] sunt p=8 numere pentru care se obţin câte m=15 numere nemarcate:
2, 4, 8, 14, 16, 22, 26, 28.
Numărul 8 se va scrie pe a doua linie a fişierului marc.out.
Trebuie sa te autentifici pentru a trimite solutii. Click aici