Eolymp-значення#12235

Eolymp-значення (Розбір)

Автор задачі:	Imran AKKI
Підготовка:	Imran AKKI
Редактор:	Hasan Saleh (MathModel)

Розв'язання Зверніть увагу, що $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, отже ми хочемо порахувати дільники числа $(1 + 2 + 3 + ... + n)$ (1+2+3+...+n). Очевидно, що не можна використати $O (n)$ , але можна зробити це за $O (n)$ \mathcal{O}(\sqrt{n}), враховуючи, що $(1 + 2 + ... + n) = \frac{n ( n + 1 )}{2}$ (1+2+...+n)=\frac{n(n+1)}{2}. Потрібно порахувати його дільники — це робиться через паралельну факторизацію: беремо парне з $n$ та $n + 1$ n+1, ділимо на 2, а потім факторизуємо, і напряму факторизуємо інше число.

Реалізація може відрізнятися. Наприклад, можна об'єднати прості факторизації, а потім порахувати дільники, як у наступній реалізації:

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):
        # беремо n/2 і (n+1), потім об'єднуємо
        a=get(n//2)
        b=get(n+1)        
    else:
        # беремо (n+1)/2 і n, потім об'єднуємо
        a=get((n+1)//2)
        b=get(n)
    # множина ключів
    s=set(list(a.keys())+list(b.keys()))
    # фінальне об'єднання
    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

Складність $O (n)$ \mathcal{O}(\sqrt{n}) з додатковими факторами $lo g$ через злиття факторизацій та структури даних.

З іншого боку, можна скористатися тим, що $τ (a \cdot b) = τ (a) \cdot τ (b)$ \tau(a \cdot b)=\tau(a) \cdot \tau(b), тобто можна окремо факторизувати обидва числа, порахувати їх дільники і перемножити.

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