Valor-Eolymp#12235

Valor-Eolymp (Editorial)

Autor del Problema:	Imran AKKI
Preparado por:	Imran AKKI
Editado por:	Hasan Saleh (MathModel)

Solución Nótese que $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 , por lo tanto queremos contar los divisores de $(1 + 2 + 3 + ... + n)$ (1+2+3+...+n) pero en poco tiempo. Es obvio que no podemos usar $O (n)$ aquí. Podemos hacerlo en $O (n)$ \mathcal{O}(\sqrt{n}) notando que $(1 + 2 + ... + n) = \frac{n ( n + 1 )}{2}$ (1+2+...+n)=\frac{n(n+1)}{2}, y queremos contar sus divisores. Esto se puede hacer con una factorización paralela: seleccionamos el par entre $n$ y $n + 1$ n+1, lo dividimos por 2, luego lo factorizamos y después factorizamos directamente el otro.

La implementación puede diferir, por ejemplo puedes unir las factorizaciones primarias y luego contar los divisores como en esta implementación:

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):
        #obtener n/2 y luego (n+1), luego unir
        a=get(n//2)
        b=get(n+1)        
    else:
        #obtener (n+1)/2 y luego n, luego unir
        a=get((n+1)//2)
        b=get(n)
    #obtener conjunto de claves comunes
    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

Complejidad $O (n)$ \mathcal{O}(\sqrt{n}) con factores adicionales de $lo g$ debido a la fusión de factorizaciones y estructuras de datos.

Por otro lado, uno puede darse cuenta de que $τ (a \cdot b) = τ (a) \cdot τ (b)$ \tau(a \cdot b)=\tau(a) \cdot \tau(b), por lo tanto puedes factorizar cada uno, obtener sus divisores y luego multiplicarlos.

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