Sono d’accordo con il tuo spoiler, però quando P > π(M) penso che a quella sommatoria vada aggiunto un numero P-π(M) di primi che, se tutti uguali al primo più grande minore di M, ci “costringono” a eseguire π(M) volte gcd() - prima avevo erroneamente usato M al posto di P.
Poi ovvio che ad esempio con O(M) memoria possiamo evitare di controllare due volte lo steso numero
Ciao,
scusami per l’estremo ritardo con cui arriva questa risposta. (La buona notizia è che le soluzioni della gara sono quasi pronte).
Ma è possibile che ciò accada? Una delle assunzioni specificava “I valori di checksum sono tutti diversi”. Questo dovrebbe escludere il caso che tu presenti, o sbaglio?
