Stavo provando a risolvere il problema Graduation Party ma non riesco a capire che metodo utilizzare per l’ultimo subtask. In pratica il mio programma calcola prima il MCD tra i primi 2 numeri, poi tra quest’ultimo valore e il terzo elemento, poi tra quest’ultimo valore e il quarto elemento e via così fino all’ultimo. Una volta finito conosco il MCD tra tutti i numeri e da qui procedo con il metodo classico di provare tutti i valori tra 1 e MCD per capire quali sono i divisori del primo numero, poi confronto questi divisori con tutti gli altri numeri e ogni volta che uno non è valido lo elimino. Il problema è che proprio questo modo di trovare i divisori è troppo inefficiente per risolvere l’ultima subtask. Qualcuno potrebbe per favore indicarmi un metodo da poter applicare? Mi basta anche un suggerimento, non serve la soluzione completa
Non è molto chiara questa parte.
Se ti interessa trovare tutti i divisori di un numero X ti basta provare tutti i valori [1, \sqrt{X} + 1]. Se sai che Y divide X allora X/Y è un divisore di X.
Grazie per il suggerimento, effettivamente era molto più semplice di quanto pensassi 