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

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

n դրական ամբողջ թվի բաժանարարների ընդհանուր քանակը գտնելու համար կարելի է 1-ից մինչև n ներառյալ բոլոր թվերը հերթով ստուգելն ու հաշվելը, թե դրանցից քանիսի վրա է n-ը բաժանվում։
Սակայն այս մոտեցումը չափազանց դանդաղ է։ Մենք կարող ենք հաշվել n-ի բաժանարարների քանակը՝ այն պարզ արտադրիչների վերլուծելով (պարզ արտադրիչների վերլուծելը պահանջում է ընդհամենը գործողություն)։
Ցանկացած թիվ կարելի է ներկայացնել իր պարզ արտադրիչների արտադրյալի տեսքով.
n-ի բաժանարարների քանակը կարելի է գտնել, եթե վերցնենք բոլոր ցուցիչները (exponents), յուրաքանչուրին գումարենք մեկ և գումարենք իրար:
Այս ամենը հնարավոր է անել մոտավորապես այնպես, ինչպես գտնում ենք 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 ≤ ):

Ելք

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

Օրինակներ

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

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