230 Divizori

[ditzone]

Aici puteţi discuta despre problema Divizori.

[•basketbalistu92]

dec eu mam bazat p metoda urm descompun in factori primi si apoi inmultesc puterile unui factor cu cele a celuilalt da m km incurc km  s fac asta adik s tot schimb vectorii intre ei

[•ucc_5]

Stie cineva care e cel mai mare factor prim al lui n ? Adica la probleme de genul acesta cand iti trebuie toti factorii primi ai unui numar (eventual un numar in jur de 1000000000), deci in care nu poti calcula cu eratostenes pentru ca iti trebuie un vector de 1 miliard, am observat ca trebuie sa iei la plesneala limita superioara a vectorului. Mai era o problema la oji in care limita superioara era considerata 32000, dar acolo iti dadeai seama ca altfel nu intra in memorie. Dar aici ? nu ar trebui sa se scrie la restrictii factorul prim maxim ?

[•pauldb]

Cel mai mare factor prim al lui N este limitat chiar de N (care poate fi prim).  Daca nu se specifica altfel, limita lui N este limita implicita si pentru factorul maxim.

Ciurul lui Eratostene nu este util in astfel de cazuri. Cand vrei sa gasesti divizorii (primi) ai unui singur numar, cel mai bine este sa faci cu metoda clasica (sa cauti divizorii pana la sqrt(N)).

[•ucc_5]

Pai tocmai din cauza asta am intrebat, dar din cate vad la problemele de genul asta, factorul prim maxim nu e maxim n (adica 2 miliarde), ci e sub 100000. Intradevar as putea calcula cu metoda clasica dar metoda asta are totusi o complexitate aproximatica O(n*sqrt(n)).
Defapt singurl motiv pentru care metoda clasica functioneaza este pentru ca factorul prim maxim este foarte mic, si cand simplificam  pe n cu factorii lui primi ca sa le aflam exponenti n ajunge sa fie mai mic decat iteratorul de cautare al factorilor primi (i<=n), si de la momentul ala nu se mai face verificarea de primalitate.

[•wefgef]

Uite cum calculezi cel mai simplu divizorii unui numar n:

Cod:

int i;
for (i = 1; i * i < n; ++i)
  if (n % i == 0)
    printf("%d %d ", i, n / i);
if (i * i == n)
  printf("%d", i);

[•ucc_5]

Am inteles si eu asta, doar e un algoritm elementar. In fine, nu mai intreb ca din cate am vazut factorul prim maxim e maxim sub un milion pentru ca nu poate fi calculat eficient altfel.
P.S. in loc de i*i nu puteai sa memorezi intr-un aux=sqrt(n) si sa parcurgi pana la aux ? adica sa nu mai faca inmultiri de i*i? Adevarul e ca, cred ca e un bug in mingw ca daca memorez intr-un auxiliar si scriu i<aux atunci programul merge foarte incet, dar daca scriu i<sqrt(n) merge foarte bine (desi ar trebui sa mearga mai incet tinand cont ca se calculeaza sqrt (n) la fiecare iterare dupa i).

[•klamathix]

Factorul prim maxim poate fi oricat , chiar n , dupa cum ti-a spus si Paul Baltescu. Wefgef ti-a oferit un algoritm care e O(sqrt(n)) indiferent de factorizarea lui n. Si e destul de evident ca daca vrei doar cel mai mare divizor prim complexitatea e aceeasi , dar se misca chiar mai bine in practica cand n nu e prim .

Cod:

for( i = 2 ; i * i <= n ; ++i ) 
     if ( n % i == 0 ) {
     divmax = i;
     while ( n % i == 0 ) n /= i;
 }

if ( n != 1 ) divmax = n ;

[•ctlin04]

Ce cazuri speciale pot aparea la problema asta, iau 80 de puncte si nu pot gasi nici un numar pentru care sa am un raspuns gresit 

[•misino]

Imi da si mie cineva niste indicatii la problema  asta ca nu ma prind cum vine?

[•Paaaulica]

De ce doar 4 puncte?
Si doar un rezultat e bun...

Cod:

#include <iostream>
#include <fstream>

using namespace std;

int st[100],N,n,a[100] ;

void inceput()
{
    ifstream f("divizori.in");
    f>>N;
    a[1]=1;
    n=1;

    for( int i=2; i<=N/2; i++)
    {
        if(N%i==0)
        {
            n++;
            a[n]=i;
        }
    }
    n++;
    a[n]=N;

}

int done=0;
void afisare(int k)
{
    ofstream g("divizori.out");
    g<<k<<endl;

    for(int i=1; i<=k; i++)
        g<<a[st[i]]<<" ";
    g<<endl;
    g.close();
    done=1;
}

int valid(int k)
{

    for(int i=1; i<=k-1; i++)
        if (st[i]==st[k])
            return 0;

    if(k>1)
    {



        if( a[st[k]] % a[st[k-1]] !=0 && a[st[k-1]] % a[st[k]]!=0 )
            return 0;


    }
    return 1;
}
void back(int k)
{
    if(done==1) return;
    for(int i=1; i<=n; i++)
    {
        st[k]=i;
        if(valid(k))
        {
            if(k==n)
                afisare(k);
            else
                back(k+1);
        }
    }
}
int main()
{

    inceput();

    back(1);


    return 0;
}

[•justsomedude]

Salut. Am incercat problema si iau 28 de puncte. Ideea si chiar implementarea au fost simplute, dar se pare ca nu si eficiente.
1) am completat vectorul A cu divizorii lui n pe care apoi urmaresc sa ii permut astfel incat sa satisfaca conditia;
2) mi-am dat seama ca impartirea asta A/A[i+1] sau A/A[i+1] inseamna div1/div2 si rezultatul este tot un divizor al lui n. Exemplu:
n= f1^k1 * f2^k2 * ... f3^k3
div1= f1^exp1 * f3^exp2 * f10^exp3
div2= f1^exp4 * f3^exp5 * f10^exp6

de dragul discutiei sa zicem ca exp1=exp4 si exp2=exp5, iar exp3=exp6+1;

atunci div1/div2=f10^1, adica f10 (un factor prim)

deci folosesc un vector 1/0  (sau true/false) destul de mare ca dimensiune

bitset <1000000005> f;  /// unde f= 1, daca i = factor prim in descompunerea lui N
                                                  = 0, altfel
SI ATUNCI AM DESCOMPUS n-ul in factor primi, completand totodata vectorul f.

3) am implementat un backtracking recursiv de generare a permutarilor multimii divizorilor unde criteriul de validare este alcatuit din 2 chestii:
a) v=0, adica sa nu fi pus deja divizorul cu indicele i in stiva
b) f[cat]=1, adica cat=nr1/nr2 sa fie numar prim...

Este ineficienta metoda? De ce iau Time Limit Exceeded pe atat de multe teste?