Programmazione 1 (P-Z) a.a. 2007-08

Si consideri il seguente tipo:

typedef struct Factor {
  unsigned long f;
  long m;
  struct Factor* next;
} Factor, *FactorList;

Scrivere una funzione con prototipo:

FactorList MultDiv (FactorList N, FactorList M);

che prende in input due liste N e M di elementi di tipo Factor tali che:

• La lista N e' ordinata in senso crescente rispetto al campo f.
• In N non ci sono due elementi con lo stesso valore del campo f.
• In N non ci sono elementi con campo m uguale a 0.

La funzione modifica la lista N come segue:

Per ogni elemento x di M:

• Se esiste un elemento y in N tale che y.f = x.f, allora la funzione pone y.m = y.m + x.m. Se dopo questa operazione, risulta y.m=0, allora l'elemento y viene eliminato dalla lista N.
• Se un tale elemento y non esiste in N, allora la funzione inserisce un nuovo elemento z in N, tale che z.f = x.f e z.m = x.m, mantenendo l'ordinamento della lista N.

La funzione MultDiv ritorna il puntatore al primo elemento della lista N cosi' modificata. La lista M non deve essere modificata. La memoria non piu' usata deve essere rilasciata.

Esempio

Se: N = {2,1}->{7,3}->{11,-2}->{19,2} e M = {13,2}->{2,-1}->{11,3}, allora la funzione modifica la lista N cosi':

N = {7,3}->{11,1}->{13,2}->{19,2}.

Scrivere un programma che prende in input un intero n e poi n triple di interi (una per linea) con formato (X Y) Z. Per ciascuna tripla il programma deve determinare se il coefficiente binomiale C(X,Y) e' divisibile o meno per Z.

Si ricorda che C(X,Y) = X!/[Y!(X-Y)!].

Esempio di Input/Output

Input:

3
(5 2) 2
(13 7) 17
(100 80) 592122

Output:

(5 2) 2 SI
(13 7) 17 NO
(100 80) 592122 SI

I numeri X, Y appartengono all'intervallo [1,10'000], mentre Z appartiene all'intervallo [2,2^32]. Quindi potreste avere a che fare con numeri molto molto grandi, come nel seguente esempio di output:

(5753 2892) 10272743 SI
(5753 2892) 1263547389 SI
(5753 2892) 441727949 NO

* Hint: Se ci pensate un po', potete usare la funzione dell'esercizio 1 come funzione di supporto.