Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-09-17 10:10:30.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:divisorgraph.in, divisorgraph.outSursăAlgoritmiada 2014, Runda Finala
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Divisorgraph

Fie un număr natural N. Se numeşte DivisorGraph al numărului N, un graf orientat cu NrDivizori(N) noduri obţinut după cum urmează:

1. Fiecărui divizor al lui N i se asociază un nod unic. De-asemenea, fiecare nod are asociat exact un divizor al lui N. Cu alte cuvinte, există o bijecţie între divizorii lui N şi nodurile grafului.
2. Pentru orice pereche (A, B) de divizori ai lui N care respectă A > B şi pentru care B îl divide pe A, se adaugă un arc orientat de la nodul asociat lui A către nodul asociat lui B.

Dându-se un graf orientat G, care se garantează că este DivisorGraph al unui număr natural, se cere cel mai mic număr care produce un DivisorGraph izomorf cu G.

Date de intrare

Fişierul de intrare divisorgraph.in ...

Date de ieşire

În fişierul de ieşire divisorgraph.out ...

Restricţii

  • 1 ≤ V ≤ 5.000
  • 1 ≤ E ≤ 500.000
  • Doua grafuri A şi B sunt izomorfe dacă şi numai dacă există o bijecţie între ele, f, astfel încât arcul f(x) -> f(y) apare în B dacă şi numai dacă arcul x -> y apare în A

Exemplu

divisorgraph.indivisorgraph.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?