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 | Teodor Plop • teodor94 |
Timp de execuție pe test | 0.35 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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. |