Ալգորիթմներ և Տվյալների Կառուցվածքներ

Երկուական աստիճանի բարձրացում

Ձեզ խնդրում են հաշվել արտահայտության արժեքը, եթե տրված են x, n և m թվերը:

Մուտք

Մուտքի միակ տողում տրված են 3 ամբողջ թվեր x, n և m (1 ≤ x, n, m ≤ ):

Ելք

Ծրագիրը պետք է տպի արտահայտության արժեքը:

Օրինակներ

Մուտք
Ելք
2 10 5
4

Բացատրություն

  1. 2^10 = 1024 ⇒ 1024 mod 5 = 4
 

Ուղեցույց

Քանի որ թվերը բավականին մեծ են, անհրաժեշտ է օգտագործել արագ աշխատող մի ալգորիթմ, որպեսզի հաշվարկը կատարվի օպտիմալ ժամանակում: Երկուական աստիճանի բարձրացումը (Binary exponentiation) չափազանց արդյունավետ մեթոդ է մեծ աստիճաններ հաշվելու համար: Այն նվազեցնում է անհրաժեշտ բազմապատկումների քանակը, ինչն էլ այն դարձնում է ավելի արագ, քան դասական տարբերակը, երբ պարզապես 1-ից n հերթով քայլելով բազմապատկում ենք արդյունքը x-ով:
 
Երկուական աստիճանի բարձրացման ալգորիթմը հիմնված է հետևյալ մաթեմատիկական սկզբունքի վրա. եթե ունենք թիվ x բարձրացված n աստիճան, ապա կարելի է ներկայացնել այսպես.
  • եթե n-ը զույգ է
  • եթե n-ը կենտ է
Այսպիսի մոտեցումը զգալիորեն կրճատում է գործողությունների քանակը, քանի որ -ը հաշվարկում ենք մեկ անգամ, ապա արդյունքները բազմապատկում: Ալգորիթմը կարող է գրվել հետևյալ կերպ.
def binpow(x, n, m):
    if n == 0:                        # Հիմնական դեպք: x^0 = 1
        return 1
    if n % 2 == 0:                    # Եթե n-ը զույգ է => հաշվարկում ենք կեսը, հետո բազմապատկում
        half = binpow(x, n // 2, m)   # հաշվում ենք կեսը
        return (half * half) % m      # արդյունք = x^(n/2) * x^(n/2)

    # եթե n-ը կենտ է => արդյունքը = x * x^(n-1)
    return (x * binpow(x, n - 1, m)) % m
Երկուական աստիճանի բարձրացման շնորհիվ, անհրաժեշտ հաշվարկների քանակը -ից նվազում է մինչև , քանի որ յուրաքանչյուր անգամ, երբ n-ը զույգ է, այն բաժանում ենք 2-ի։ Կարևոր է նաև նշել, որ եթե որևէ քայլում n-ը կենտ է, ապա հաջորդ քայլին այն դառնում է զույգ:
Եկեք մի քանի արժեքների վրա տեսնենք թե ալգորիթմի ինչպես է աշխատում.
x = 2, n = 10 (m-ը չենք հաշվի պարզության համար)
  1. [n = 10] → n % 2 == 0 ⇒ հաշվում ենք binpow(2, 5)
  1. [n = 5] → n % 2 ≠ 0 ⇒ վերադարձնում ենք 2 * binpow(2, 4)
  1. [n = 4] → n % 2 == 0 ⇒ հաշվում ենք binpow(2, 2)
  1. [n = 2] → n % 2 == 0 ⇒ հաշվում ենք binpow(2, 1)
  1. [n = 1] ⇒ n % 2 ≠ 0 ⇒ վերադարձնում ենք 2 * binpow(2, 0)
  1. [n = 0] ⇒ n == 0 ⇒ վերադարձնում ենք 1
  1. [մինչև n = 1] ⇒ վերադարձնում ենք 2 * 1 = 2
  1. [մինչև n = 2] ⇒ վերադարձնում ենք 2 * 2 = 4
  1. [մինչև n = 4] ⇒ վերադարձնում ենք 4 * 4 = 16
  1. [մինչև n = 5] ⇒ վերադարձնում ենք 2 * 16 ⇒ 32
  1. [մինչև n = 10] ⇒ վերադարձնում ենք 32 * 32 = 1024
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue