Eolymp-value#12235

Eolymp-value (Editorial)

Problem Author:	Imran AKKI
Prepared by:	Imran AKKI
Edited by:	Hasan Saleh (MathModel)

Solution Notice that $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 , thus we want to count the divisors of $(1 + 2 + 3 + ... + n)$ (1+2+3+...+n) but in short time , it's obvious that we cannot use $O (n)$ here , We can do this in $O (n)$ \mathcal{O}(\sqrt{n}) by noticing that $(1 + 2 + ... + n) = \frac{n ( n + 1 )}{2}$ (1+2+...+n)=\frac{n(n+1)}{2} , want to count it's divisors , this can be done by doing a parallel factorization , we select the even of $n$ and $n + 1$ n+1 and divide it by 2 and then factorize it and then directly factorize the others.

The implementation may differ , for example you may merge prime factorizations and then count the divisors like this implementation:

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):
        #get n/2 and then (n+1) then merge
        a=get(n//2)
        b=get(n+1)        
    else:
        #get (n+1)/2 and the n then merge
        a=get((n+1)//2)
        b=get(n)
    #get set of common keys
    s=set(list(a.keys())+list(b.keys()))
    #final
    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

Complexity $O (n)$ \mathcal{O}(\sqrt{n}) with additional $lo g$ factors due to prime factorization merging and data structures.

On the other hand , The one may realize the $τ (a \cdot b) = τ (a) \cdot τ (b)$ \tau(a \cdot b)=\tau(a) \cdot \tau(b) thus you can factorize each of them , getting it's divisors and then multiply them.

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