Fişierul intrare/ieşire:cntgcd.in, cntgcd.outSursăONI 2013, Baraj
AutorMihai CalanceaAdăugată descipianusFMI Ciprian Olariu scipianus
Timp execuţie pe test0.35 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cntgcd

Se consideră numerele naturale nenule N şi D.

Cerinţă

Să se determine numărul perechilor de numere A şi B, ambele mai mici sau egale cu N şi cu proprietatea că cel mai mare divizor comun al lor este D.

Date de intrare

Fişierul de intrare cntgcd.in se află numerele N şi D separate printr-un spaţiu.

Date de ieşire

În fişierul de ieşire cntgcd.out va conţine un singur număr natural reprezentând numărul perechilor de numere naturale care au cel mai mare divizor comun al lor egal cu D.

Restricţii

  • 1 < N ≤ 109
  • 0 < D ≤ N
  • Pentru 40% din punctaj 1 < N ≤ 106
  • Pentru 75% din punctaj 1 < N ≤ 108
  • Perechea (A, B) se consideră a fi aceeaşi cu perechea (B, A)

Exemplu

cntgcd.incntgcd.out
20 5
6

Explicaţie

Cele 6 perechi sunt: (5, 5) (5, 10) (5, 15) (5, 20) (10, 15) (15, 20)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content