Fie a
și b
două numere naturale 0 < a ≤ b
.
Cerința
Să se determine numărul de fracții \( \frac{x}{y} \) diferite, ce se pot forma utilizând numere naturale nenule, având proprietățile:
- \( \frac{a}{b} \leq \frac{x}{y} \leq \frac{b}{a} \)
2 ≤ x + y ≤ a + b
Exemplu: Pentru a = 2
și b = 4
există 9
fracții diferite cu proprietățile \( \frac{2}{4} \leq \frac{x}{y} \leq \frac{4}{2} \) și 2 ≤ x + y ≤ 6
și anume \( \frac{2}{4}, \frac{1}{1}, \frac{2}{2}, \frac{3}{3}, \frac{2}{1}, \frac{1}{2}, \frac{2}{3}, \frac{3}{2}, \frac{4}{2} \)
Date de intrare
Fișierul de intrare nfrac.in
conţine pe prima linie un număr natural T
, iar pe fiecare din următoarele T
linii câte o pereche de numere a
și b
cu semnificaţia de mai sus.
Date de ieșire
Fișierul de ieșire nfrac.out
va conţine T
linii. Pe linia i
, 1 ≤ i ≤ T
, se va afișa numărul de fracții cerut, corespunzător perechii aflate pe linia i + 1
din fișierul de intrare.
Restricții și precizări
0 < a ≤ b ≤ 1.000.000
;1 ≤ T ≤ 100
;- Două fracții
x1 / y1
șix2 / y2
se consideră distincte dacăx1 ≠ x2
sauy1 ≠ y2
;
Exemplu:
nfrac.in
3 2 4 128 256 12345 56789
nfrac.out
9 24768 1536317971
Explicație
În fișierul de intrare se găsesc T = 3
perechi de numere.
Există 9
fracții cu proprietățile: \( \frac{2}{4} \leq \frac{x}{y} \leq \frac{4}{2} \) și 2 ≤ x + y ≤ 6
Există 24768
fracții cu proprietățile: \( \frac{128}{256} \leq \frac{x}{y} \leq \frac{256}{128} \) și 2 ≤ x + y ≤ 384
Există 1536317971
fracții cu proprietățile: \( \frac{12345}{56789} \leq \frac{x}{y} \leq \frac{56789}{12345} \) și 2 ≤ x + y ≤ 69134