Valeur-Eolymp#12235

Valeur-Eolymp (Corrigé)

Auteur du problème:	Imran AKKI
Préparé par:	Imran AKKI
Édité par:	Hasan Saleh (MathModel)

Solution Remarquez 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, donc nous voulons compter les diviseurs de $(1 + 2 + 3 + ... + n)$ (1+2+3+...+n) mais en peu de temps. Il est évident que nous ne pouvons pas utiliser $O (n)$ ici. Nous pouvons le faire en $O (n)$ \mathcal{O}(\sqrt{n}) en remarquant que $(1 + 2 + ... + n) = \frac{n ( n + 1 )}{2}$ (1+2+...+n)=\frac{n(n+1)}{2}. Nous voulons compter ses diviseurs, cela peut être fait en réalisant une factorisation parallèle : nous choisissons le pair entre $n$ et $n + 1$ n+1, nous le divisons par 2 puis nous le factorisons, ensuite nous factorisons directement l'autre.

L'implémentation peut varier, par exemple vous pouvez fusionner les factorisations premières et ensuite compter les diviseurs comme dans cette implémentation :

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):
        # prendre n/2 puis (n+1) et fusionner
        a=get(n//2)
        b=get(n+1)        
    else:
        # prendre (n+1)/2 puis n et fusionner
        a=get((n+1)//2)
        b=get(n)
    # obtenir l'ensemble des clés communes
    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

Complexité $O (n)$ \mathcal{O}(\sqrt{n}) avec des facteurs supplémentaires en $lo g$ dus à la fusion des factorisations premières et aux structures de données.

D'un autre côté, on peut remarquer que $τ (a \cdot b) = τ (a) \cdot τ (b)$ \tau(a \cdot b)=\tau(a) \cdot \tau(b), donc vous pouvez factoriser chacun d'eux, obtenir leurs diviseurs puis multiplier.

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