Sürətli dərəcəyə yüksəltmə#2814

Sürətli dərəcəyə yüksəltmə

1 saniyə

128 meqabayt

Asan

Çox vaxt $x^{n}$ x^n ifadəsinin səmərəli hesablanması problemi yaranır. Burada x və n verilmişdir, n isə müsbət tam ədəddir.

Məsələn, $x^{16}$ x^{16} hesablanmalıdırsa, sadəcə x-i $15$ dəfə x-ə vurmaqla nəticə əldə etmək olar. Lakin, eyni nəticəyə sadəcə dörd vurma əməliyyatı ilə də nail olmaq mümkündür: nəticəni ardıcıl kvadratlaşdırmaqla $x^{2}$ x^2, $x^{4}$ x^4, $x^{8}$ x^8, $x^{16}$ x^{16}-nı hesablaya bilərik.

Bu ideyanı ümumiyyətlə n-in istənilən qiymətinə tətbiq etmək olar. Bunun üçün n-i ikilik yazılışında göstəririk (aparıcı sıfırları atmadan). Sonra hər bir "1" hərfini SX hərflər cütü ilə, hər bir "0" hərfini isə S hərfi ilə əvəz edirik və ən soldakı SX cütünü atırıq. Nəticədə $x^{n}$ x^n-in hesablanması üçün qayda alınır; burada "S" kvadratlaşdırmanı, "X" isə x-ə vurmanı göstərir. Məsələn, n = 23 üçün ikilik yazılış 10111-dir. Beləliklə, SXSSXSXSX ardıcıllığı yaranır. Əvvəlki SX cütünü atırıq və son qayda SSXSXSX alınır. Bu belə başa düşülür: "kvadratlaşdır, kvadratlaşdır, x-ə vur, kvadratlaşdır, x-ə vur, kvadratlaşdır və x-ə vur"; yəni ardıcıl olaraq $x^{2}$ x^2, $x^{4}$ x^4, $x^{5}$ x^5, $x^{10}$ x^{10}, $x^{11}$ x^{11}, $x^{22}$ x^{22}, $x^{23}$ x^{23} hesablamaq lazımdır.

Verilmiş n üçün $x^{n}$ x^n-in sürətli hesablanması qaydasını qurmalısınız.

Giriş

Bir müsbət tam ədəd n ( $2 \cdot 1 0^{9}$ 2 \cdot 10^9-dan böyük olmayan).

Çıxış

$x^{n}$ x^n-i hesablamaq üçün qaydanı ifadə edən sətri çap edin.

Nümunələr

Nümunə 1

Loading

x^{n}

x^{16}

x^{2}

x^{4}

x^{8}

x^{16}

x^{n}

x^{2}

x^{4}

x^{5}

x^{10}

x^{11}

x^{22}

x^{23}

x^{n}

2 \cdot 1 0^{9}

x^{n}