Fișierul intrare/ieșire marc.in, marc.out Sursă Olimpiada pe Sector 2011, Clasa a 10-a
Autor Carmen Mincă | Doina Druță Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.35 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty

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.in marc.out Explicatie
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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii