Ogroman problem sa Pericom (Algoritam)!!!

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.

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

Potpis

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

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