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

Բաժանարարների քանակի հաշվումը պարզ արտադրիչների վերլուծելու միջոցով

n դրական ամբողջ թվի բաժանարարների ընդհանուր քանակը գտնելու համար կարելի է 1-ից մինչև n ներառյալ բոլոր թվերը հերթով ստուգելն ու հաշվելը, թե դրանցից քանիսի վրա է n-ը բաժանվում։

Սակայն այս մոտեցումը չափազանց դանդաղ է։ Մենք կարող ենք հաշվել n-ի բաժանարարների քանակը՝ այն պարզ արտադրիչների վերլուծելով (պարզ արտադրիչների վերլուծելը պահանջում է ընդհամենը O(n)\mathcal{O}(\sqrt{n}) գործողություն)։

Ցանկացած թիվ կարելի է ներկայացնել իր պարզ արտադրիչների արտադրյալի տեսքով.

2=214=227=7124=23⋅3175=31⋅5284=22⋅31⋅71300=22⋅31⋅52n=p1e1⋅p2e2⋅p3e3⋅...⋅pkek\begin{aligned} 2 &= 2^1 \\ 4 &= 2^2 \\ 7 &= 7^1 \\ 24 &= 2^3 \cdot 3^1 \\ 75 &= 3^1 \cdot 5^2 \\ 84 &= 2^2 \cdot 3^1 \cdot 7^1 \\ 300 &= 2^2 \cdot 3^1 \cdot 5^2\\ n &= p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot ... \cdot p_k^{e_k} \\ \end{aligned}

n-ի բաժանարարների քանակը կարելի է գտնել, եթե վերցնենք բոլոր ցուցիչները (exponents), յուրաքանչուրին գումարենք մեկ և գումարենք իրար:

2=21  ⟹  1+1=24=22  ⟹  2+1=37=71  ⟹  1+1=224=23⋅31  ⟹  (3+1)⋅(1+1)=875=31⋅52  ⟹  (1+1)⋅(2+1)=684=22⋅31⋅71  ⟹  (2+1)⋅(1+1)⋅(1+1)=12300=22⋅31⋅52  ⟹  (2+1)⋅(1+1)⋅(2+1)=18n=p1e1⋅p2e2⋅p3e3⋅...⋅pkek  ⟹  (e1+1)⋅(e2+1)⋅(e3+1)\begin{aligned} 2 &= 2^1 &&\implies 1 + 1 &&= 2\\ 4 &= 2^2 &&\implies 2 + 1 &&= 3\\ 7 &= 7^1 &&\implies 1 + 1 &&= 2\\ 24 &= 2^3 \cdot 3^1 &&\implies (3 + 1) \cdot (1 + 1) &&= 8\\ 75 &= 3^1 \cdot 5^2 &&\implies (1 + 1) \cdot (2 + 1) &&= 6\\ 84 &= 2^2 \cdot 3^1 \cdot 7^1 &&\implies (2 + 1) \cdot (1 + 1) \cdot (1 + 1) &&= 12\\ 300 &= 2^2 \cdot 3^1 \cdot 5^2 &&\implies (2 + 1) \cdot (1 + 1) \cdot (2 + 1) &&= 18\\ n &= p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot ... \cdot p_k^{e_k} &&\implies (e_1 + 1) \cdot (e_2 + 1) \cdot (e_3 + 1) \\ \end{aligned}

Այս ամենը հնարավոր է անել մոտավորապես այնպես, ինչպես գտնում ենք n-ի պարզ արտադրիչների վերլուծությունը:

n = ...
p, divisors = 1, 1          # պարզ բաժանարարը և բաժանարարների քանակը

while p * p <= n:           # քանի դեռ p <= sqrt(n)
    p += 1                  # Ամեն քայլի p-ն 1-ով մեծացնում ենք
    if n % p != 0:          # Եթե n-ը p-ով չի բաժանվում, անցնում ենք առաջ
        continue
    
    exp = 0                 # ցուցիչի հաշվիչ
    while n % p == 0:       # բաժանել այնքան, որքան հնարավոր է
        n //= p
        exp += 1
    divisors *= exp + 1     # թարմացնում ենք արտադրյալը (բաժանարարների քանակը)

if n > 1:                   # եթե p > sqrt(n) => n-ը ինքն է հենց պարզ արտադրիչ
    divisors *= 2           # n-ի ցուցիչը հավասար է 1-ի
print(divisors)

Առաջադրանք: Գտնել n-ի բաժանարարների քանակը

Ձեզ խնդրում են գրել ծրագիր, որը ստանալով n ամբողջ թիվը, պետք է հաշվի n-ի բաժանարարների քանակը:

Մուտք

Մուտքի առաջին տողում տրված է n ամբողջ թիվը (2 ≤ n ≤ 10910^9):

Ելք

Ծրագիրը պետք է տպի n-ի բաժանարարների քանակը:

Օրինակներ

Մուտք

Ելք

8

4

17

2

2048

12

48

10

Բոնուս: Ինչո՞ւ է ցուցիչներին (exponents) 1 գումարելը և բոլոր ստացված արժեքները իրար վրա բազմացնելը տալիս n-ի բաժանարարների քանակը:

Բաժանարարների քանակը գտնելու հիմքում ընկած է այն միտքը, որ ցանկացած բաժանարար կարելի է դիտարկել որպես արտադրիչ պարզ թվերի որոշ համադրություն։ Յուրաքանչյուր արտադրիչի ցուցիչը ցույց է տալիս, թե քանի անգամ կարելի է այն ներգրավել n-ի մեջ։ Երբ ցուցիչին գումարում ենք 1, դա ընդգրկում է նաև «0 անգամ» տարբերակը (երբ տվյալ պարզ արտադրիչը չի օգտագործվում), ինչը համապատասխանում է n-ին ինչպես նաև հաշվի է առնում 1-ը որպես բաժանարար։ Վերջնական արդյունքը, երբ բազմապատկում ենք (exponent + 1)-երը, ստանում ենք բոլոր հնարավոր համադրությունների քանակը, այսինքն n թվի բոլոր բաժանարարների քանակը:

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB