Cədvəli göndərmək#1563

Cədvəli göndərmək

1 saniyə

128 meqabayt

Çox asan

Jimmy $f (x, y)$ f(x, y) funksiyasını hesablamaq lazımdır; burada $x$ və $y$ $1$ -dən $n$ -ə qədər ədədlərdir. Əgər o, $f (x, y)$ f(x, y)-i bilirsə, istənilən tam $k$ üçün $f (k \cdot x, k \cdot y)$ f(k \cdot x, k \cdot y)-ni sadə hesablamalarla $f (x, y)$ f(x, y) və $k$ -dan istifadə edərək asanlıqla çıxara bilər.

Qeyd edək ki, $f$ funksiyası simmetrik deyil, yəni $f (x, y)$ f(x, y) $f (y, x)$ f(y, x)-dən çıxarıla bilməz.

Məsələn, əgər $n = 4$ n = 4-dürsə, Jimmy əvvəlcə $16$ mümkün cütdən $11$ -ni bilməlidir:

Qalan $5$ dəyəri isə artıq məlum olanlardan çıxarmaq olar:

$f (2, 2)$ f(2, 2), $f (3, 3)$ f(3, 3) və $f (4, 4)$ f(4, 4) — $f (1, 1)$ f(1, 1)-dən;
$f (2, 4)$ f(2, 4) — $f (1, 2)$ f(1, 2)-dən;
$f (4, 2)$ f(4, 2) — $f (2, 1)$ f(2, 1)-dən;

Giriş

Girişdə ən çoxu $600$ sətir verilir. Hər sətirdə bir tam $n$ ədədi verilir ( $1 \leq n \leq 50000$ 1 \le n \le 50000). Son sətir $0$ -dır və emal edilməməlidir.

Çıxış

Girişdəki hər $n$ üçün ayrıca sətirdə Jimmy-nin bütün $n^{2}$ n^2 dəyəri $f (x, y)$ f(x, y) hesablamaq üçün bilməli olduğu ən azı neçə funksiya dəyəri lazım olduğunu çap edin.

Nümunələr

Nümunə 1

Loading

f (x, y)

f (x, y)

f (k \cdot x, k \cdot y)

f (x, y)

f (x, y)

f (y, x)

n = 4

f (2, 2)

f (3, 3)

f (4, 4)

f (1, 1)

f (2, 4)

f (1, 2)

f (4, 2)

f (2, 1)

1 \leq n \leq 50000

n^{2}

f (x, y)