Eolymp-dəyəri#12235

Eolymp-dəyəri (Həll təhlili)

Müəllif:	Imran AKKI
Hazırlayan:	Imran AKKI
Redaktor:	Hasan Saleh (MathModel)

Həll Qeyd edin ki, $f (n, k) \equiv (1 + 2 + 3 + ... + n) mod k ⟹ f (n, k) \equiv (1 + 2 + 3 + ... + n) mod k = 0$ f(n,k) \equiv (1+2+3+...+n) \bmod k \implies f(n,k) \equiv (1+2+3+...+n) \bmod k=0 , yəni biz $(1 + 2 + 3 + ... + n)$ (1+2+3+...+n) ifadəsinin bölənlərini saymaq istəyirik, amma qısa vaxtda. Aydındır ki, burada $O (n)$ işlətmək olmaz. Bunu $O (n)$ \mathcal{O}(\sqrt{n})-də edə bilərik, çünki $(1 + 2 + ... + n) = \frac{n ( n + 1 )}{2}$ (1+2+...+n)=\frac{n(n+1)}{2} olur, və biz onun bölənlərini saymalıyıq. Bunun üçün paralel faktorizasiyadan istifadə edə bilərik: $n$ və $n + 1$ n+1-dən cüt olanı seçirik və onu 2-yə bölüb faktorlaşdırırıq, sonra digərini birbaşa faktorlaşdırırıq.

İmplementasiya fərqli ola bilər, məsələn sadəcə sadə ədədlərin faktorizasiyalarını birləşdirib bölənlərin sayını hesablamaq olar. Məsələn belə:

from math import *
from collections import defaultdict as dd

def get(x):
    y=x
    fact=dd(int)
    for i in range(2,x+1):
        if(y==1):
            break
        if(i>sqrt(y)):
            break
        else:
            while(y%i==0):
                fact[i]+=1
                y//=i
    if(y!=1):
        fact[y]+=1
    return fact

def solve():
    n=int(input())
    if(n%2==0):
        # əvvəl n/2, sonra (n+1) götür, sonra birləşdir
        a=get(n//2)
        b=get(n+1)        
    else:
        # əvvəl (n+1)/2, sonra n götür, sonra birləşdir
        a=get((n+1)//2)
        b=get(n)
    # açarların birləşmiş dəsti
    s=set(list(a.keys())+list(b.keys()))
    # yekun
    final=dd(int)
    for i in list(a.keys()):final[i]+=a[i]
    for i in list(b.keys()):final[i]+=b[i]
    p=1
    for i in list(final.values()):
        p*=(i+1)
    print(p)
        
for _ in range(int(input())):
    solve()

Python

Mürəkkəblik $O (n)$ \mathcal{O}(\sqrt{n}) olur, əlavə $lo g$ faktorları isə sadə ədədlərə ayırma və məlumat strukturlarının birləşdirilməsindən gəlir.

Digər tərəfdən, $τ (a \cdot b) = τ (a) \cdot τ (b)$ \tau(a \cdot b)=\tau(a) \cdot \tau(b) faktını bilsək, hər birini ayrı-ayrılıqda faktorlaşdırıb bölənlərini hesablaya və sonra hasilini tapa bilərik.

from math import *

def d(x):
    s=set()
    for i in range(1,int(sqrt(x))+1):
        if(x%i==0):
            s.add(i)
            s.add(x//i)
    return len(s)
for _ in range(int(input())):
    n=int(input())
    if(n%2==0):
        print(d(n//2)*d(n+1))
    else:
        print(d((n+1)//2)*d(n))

Python