073 Perechi

[•caen1]

Am reusit sa o rezolv de 100 verificand daca N este prim inainte de a calcula rezultatul. Asta ar fi solutia corecta?

[•MciprianM]

Pentru a afla divizorii unui numar poti face asa:

Cod:

for ( d = 2; d * d <= n; ++ d ){
        if ( n % d == 0 )
                scrie d si n/d
}

Astfel in O(sqrt(n)) putem afla toti divizorii! Totusi atentie la patrate perfecte!(9, 16, ...)
Pentru descompunere in factori primi, putem face similar:

Cod:

k = 0;
for ( d = 2; d * d <= n; ++ d ){
        if ( n%d==0 ){     p [ k ]  = d; e [ k ] = 0; k ++;}
        while ( n % d == 0 ){
                e [ k - 1] ++;
                n/=d;
         }
}
if ( n > 1 ){p[k]=n;e[k ]=1;k++;}

[•ctlin04]

cei care au gasit solutia problemei cmmmc de la ONI 2010, dati-mi si mie va rog un link, ca tot caut sa nu pot gasi nimic

[•Magnus]

Cred ca ar fi mai bine sa postezi aici pentru ca problema cmmmc este si pe infoarena.

[•ctlin04]

defapt, de acolo doaream sa aflu formula pentru a rezolva anume aceasta problema

[•Magnus]

Oricum, daca esti interesat de problema cmmmc, e mai bine sa postezi acolo. Daca nu, atunci spune ca esti interesat de perechi.
Uite un hint pentru perechi.

Daca ai n=a₁^d₁*a₂^d₂*...*a_k^d_k considera vectorul d.
pentru fiecare element i te gandesti asa:
1. exista un caz in care si numarul x si numarul y au in componenta a_i^d_i.
2. exista un caz in care numarul x contine a_i^d_i, iar y are a_i in componenta dar nu de suficient de multe ori.
3. exista un caz in care numarul y contine a_i^d_i, iar x are a_i in componenta dar nu de suficient de multe ori.

nici x, nici y nu vor avea a_i in componenta la un exponent mai mare de d_i.

Si nu depinde de cum alegi pentru i ca sa alegi pentru j.

Daca vreun admin/moderator considera ca am zis un prea mult il rog sa-mi stearga postul.

[•ctlin04]

Poate sa-mi dea careva vreo sugestie de ce am intruna NON ZERO EXIT STATUS la testul 9, pls?

[•Stefex09]

eu nu am facut descompunerea in factori
in for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
calculez cmmdc i si j si calculez cmmmc cu formula cmmmc=(a*b)/cmmdc(a,b) (formula tine)
si iau TLE la majoritatea (iau 15 puncte) cum ar trb sa fac?

[•elfus]

Stefane, vezi ca ai complexitatea O(N^2) care e prea mare aici. In mod normal cu N^2 intra pentru N <= 1000. Intra si tu pe fb si iti zic acolo cum sa faci, nu pot sa scriu aici solutia (sau citeste postu' lu Magnus de mai sus).

[•pauldb]

De fapt el are O(N^2 log N), deoarece calculeaza la fiecare pas cmmdc-ul.

[•visanr]

Imi puteti spune si mie care ar fi motivul pt care iau incorect pe testul 7? http://infoarena.ro/job_detail/741411
Am trimis in cateva luni peste 80 de surse, nu pot lua 100...

[•dushmi]

Cred ca greseala ta este in urmatoarea parte a codului:

Cod:

if(n>1) factors.push_back(n);

Trebuie sa fie:

Cod:

factors.push_back(1);

[•visanr]

Asta era, multumesc mult!

[•RaduGabriel2012]

Hint : cmmmc a doua nr nu poate fi = cu n daca produsul lor e mai mic ca n.

[•DxH5dIMHN]

Finally! Cred ca acum merge si pentru N>2^31 - Pentru N=6227020800 exista 1584 divizori si 15592 de perechi gasite sub 0,5 secunde (in medie 400-450 ms) - Nu stiu daca valorile sunt trunchiate 

[•Dddarius95]

va rog sa ma ajutati...iau 90p...incorect pe testele 9 si 18.......
am gasit o formula in care apar exponentii numerelor prime din descompunerea lui n in factori.... totusi da incorect pe 2 teste si nu stiu de ce.....am scris tot codul de la capat si degeaba... e vreun caz special ceva?
LE:

Cod:

void Solve()
{
    for(int i=1;i<=k && n!=1;i++)
        if(n % P[i]==0)
        {
            int exp=0;
            while(n % P[i]==0)n/=P[i],exp++;
            //formula-sol
        }

    
    g<<sol<<'\n';

}

[•vendetta]

Pierzi cazul cand n > 1( dupa ce l-ai descompuns in factori primi ). Trateaza acest caz si o sa iei 100.

[•Dddarius95]

da...ai avut dreptate...ms mult....nu observasem treaba asta....si trimisesem 5000 de surse:D....ms mult...voi fi mai atent pe viitor

[•patcasrares]

ce se intampa daca n e prim

[•Trixer]

Daca n e prim atunci vei avea doar 2 perechi: (1, n), (n, n).

[•Coroian_David]

Salut!
iau 10 puncte si nu inteleg de ce, am folosit formula: ((exp1 * 2 + 1) * (exp2 * 2 + 1) * ... * (expn * 2 + 1) + 1) / 2

LE : am 100.