eolymp
bolt
Try our new interface for solving problems
Məsələlər

Zəncirvari kəsr

Zəncirvari kəsr

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Zəncirvari kəsr aşağıdakı şəkildədir:

Bu ifadədə a_0 tam ədəd, qalan a_n-lər isə müsbət tam ədədlərdir. Zəncirvari kəsrlər ona görə maraqlıdır ki, onun köməyi ilə istənilən həqiqi ədədi yazmaq olur. Bu zaman rasional ədədlər üçün kəsr sonlu, irrasionallar üçünsə sonsuz olacaq. Məsələn, 9/4 ədədi üçün zəncirvarı kəsr belə olacaq: 9/4 = 2 + 1/(3+1/1).

Bu kəsri isə belə də göstərmək olar: 9/4 = 2 + 1/4.

Sizin vəzifəniz verilmiş rasional p/q üçün zəncirvari kəsr şəklində ən kiçik təsviri tapasınız.

Giriş verilənləri

Giriş faylının birinci sətrində iki tam pq (1 <= p; q <= 10^3) ədədləri yerləşir.

Çıxış verilənləri

Çıxış faylının birinci sətrində zəncirvari kəsrin p/q-yə bərabər olan elementlərinin sayı olan n ədədi verilir. İkinci sətirdə arada boşluq işarəsi olmaqla a_0, a_1, ..., a_n ədədləri çıxışa verilir.

Nümunə

Giriş verilənləri #1
9 4
Çıxış verilənləri #1
2
2 4