[es] - Ogroman problem sa Pericom (Algoritam)!!!

Lekic
E moj prijatelju
SER BIH

Član broj: 15506
Poruke: 142
77.46.246.*

Profil

Ogroman problem sa Pericom (Algoritam)!!!

^{24.01.2008. u 00:32 - pre 197 meseci}

Da li iko uopste ima ideju kako ovo da se uradi??? Bar neki pocetak, ideja, neki algoritam ili tako nesto??? Posle bi trebao da to otkucam u javi da radi posao za manje od jedne sekunde!

-----------------------------------------------------

Perica je dobio spisak od nastavnika od n (n<=1000) i jedan prirodan broj koji nije veci od milijardu. Perica treba da utvrdi na koliko nacina moze izabrati neki podskup od brojeva koje je dobio od nastavnika, tako da njihov proizvod bude deljiv brojem c. Kako ukupan broj resenja moze biti ogroman, potrebno je naci ostatak tog broja pri deljenju sa 999983.

ULAZ:
U prvom redu datoteke proizvodi.in su brojevi n i c. U sledecih n redova su brojevi koje je Perica dobio od nastavnika. (Brojeve koje je dobio nisu veci od 1000000)

IZLAZ:
U prvom redu datoteke proizvodi.out ispisati trazeni broj podskupova.

-----------------------------------------------------

Svi hoce u raj, a niko nece da umre...

Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
*.ADSL.neobee.net.

+1 Profil

Re: Ogroman problem sa Pericom (Algoritam)!!!

^{24.01.2008. u 09:42 - pre 197 meseci}

Pod pretpostavkom da je c broj koji nije veci od milijardu,

resenje je vrlo jednostavno:

Nadji sve proste faktore broja C i izbaci ih iz skupa brojeva koji je perica dobio od nastavnika.
Moras samo voditi racuna da li se ti prosti faktori nalaze u nekom od brojeva koje si izbacio kao faktori.
Bilo koji podskup preostalih brojeva pomnozen sa izbacenim skupom ti daje broj deljiv sa C.

primer:

C = 45

lista brojeva:

2,3,3,4,4,5,7,9

prosti faktori C su 3,3,5

znaci

svi podskupovi skupa (2,4,4,7,9) izmnozeni i pomnozeni sa (3*3*5) ti daju broj deljiv sa C
i podskupovi skupa (2,3,3,4,4,7) izmnozeni i pomnozeni sa (5*9) ti daju broj deljiv sa C

Znaci rezultat je broj podskupova (2,4,4,7,9) + broj podskupova (2,3,3,4,4,7)

Drugi nacin da se dobije na koliko nacina se moze izabrati skup ciji proizvod je deljiv sa C jeste
da izracunas ukupan broj podskupova spiska i oduzmes sve kombinacije u kojima ucestvuju prosti faktori
broja C

Odgovor na temu

Lekic
E moj prijatelju
SER BIH

Član broj: 15506
Poruke: 142
91.150.113.*

Profil

Re: Ogroman problem sa Pericom (Algoritam)!!!

^{24.01.2008. u 12:09 - pre 197 meseci}

E hvala ti puno, jeste da sam smislio i uradio pre nego sto sam ovo procitao, al nema veze... Genijalna ideja, hvala ti puno!

Svi hoce u raj, a niko nece da umre...

Odgovor na temu