Non riesco a risolvere l’esercizio “Armadio”, della gara practice dei nazionali di dopodomani, quindi non penso di essere tenuto a condividerlo qui
Se qualcuno con il testo a disposizione riuscisse a darmi anche solo una dritta sarebbe apprezzata
Al momento riesco ad implementare una soluzione molto molto basic con un semplice brute force di tutte le coppie di numeri a e b e controlla poi se la coppia di numeri rende valida l’espressione
Tuttavia passa giusto i primi 3 subtask e nonostante le diverse ore passate a tracciare grafici improbabili per trovare delle relazioni non riesco a trovare un modo per scindere un numero per far passare la complessita’ di un singolo numero da n^2 a n log(n) minimo
I primi subtask richiedono una complessita’ inferiore a n^2, quelli intermedi n log(n) (ho supposto fosse log base 2 ma non ne sono certo) oppure n sqrt(n) e gli ultimi q log(n)
Considera che a + b + gcd(a, b) = n implica gcd(a, b) divide n; dunque, detti p e q interi coprimi tra loro tali che a = pgcd(a, b) e b = qgcd(a, b), per ogni d = gcd(a, b) divisore di n l’equazione data si riduce a p + q = r - 1, con r = n/d; Eulero sa quanti sono i naturali coprimi con r - 1 e non ci vuole molto a precalcolare questa sapienza per n che va da 1 a 4*1e6.
Ricorda che a, b sono naturali non nulli, pertanto non ci sono soluzioni con n < 3.
Con queste idee e tenendo presente che i codivisori vanno a coppie, con il caso speciale dei quadrati che hanno anche un divisore codivisore di se stesso, per ora ho scritto una soluzione da 84/100, che però passa tutti i testcase tranne il primo del subtask 10 e il primo del subtask 11, per i quali dà wrong answer senza che per ora io abbia capito perché.
Con queste idee e tenendo presente che i codivisori vanno a coppie, con il caso speciale dei quadrati che hanno anche un divisore codivisore di se stesso, per ora ho scritto una soluzione da 84/100, che però passa tutti i testcase tranne il primo del subtask 10 e il primo del subtask 11, per i quali dà wrong answer senza che per ora io abbia capito perché.
ad essere sincero non capisco queste ultime 4 righe e non capisco il termine codivisore.
qui sotto riporto se ti aiuta quello che ho fatto per prendere 100 :
trova tutte le soluzioni data una n a+b+gcd(a,b)==n
> 1)a è divisibile per il gcd(a,b) per definizione
> 2)b è divisibile per il gcd(a,b)per definizione
> 3)il gcd(a,b) è divisibile per se stesso uwu
se tutti questi argomenti hanno un fattore in comune, implica che n per essere intero, sia
divisible dal gcd(a,b);
adesso arriva la parte difficile, se il gcd sia uguale ad x stiamo imponendo che una volta
tolto il gcd da a e b essi saranno coprimi fra loro (stiamo togliendo il più grande
divisore in comune );
se analizziamo la funzione di eulero cosa ci dice per ogni numero x?
prendo un numero x e ti restituisco quanti numeri sono coprimi con esso.
bhe si ma vediamola in un altro modo:
perchè questa funzione è uguale al numero di soluzioni per l equazione a/gcd(a,b)+b/gcd(a,b)=n/gcd(a,b)-gcd(a,b)/gcd(a,b)
scritta in maniera più umana x+y=k-1
dove x y e k-1 sono coprimi fra di loro
se ci fate caso la funzione di eulero \forall x>1 -> f(x)mod2==0
strano no?
la dimostrazione è facile se prendo un intero qualunque facciamo n
sottraggo ad n un coprimo ,n-x sarà coprimo e sappiamo che n-x e x sono pure loro
coprimi fra di loro perchè?
se per assurdo x e n-x hanno un fattore comune esempio y y*(x)+y*(n-x)==n
andrebbe in conflitto con la nostra tesi poichè n sarà divisibile per y e quindi y*(x) e y*
(n-x) non sono coprimi
l esercizio quindi si può risolvere, perchè formalmente vuole sapere fissato un gcd valido
,ovvero sottomultiplo di n quante sono le soluzioni di : x+y=k-1
posso ricondurmi al fatto che la se la funzione toziente restituisse un array
posso prendere il primo e ultimo elemento il secondo e il penultimo ecc.ecc e valgono le
seguenti proprietà:
1)toziente[n-i] e toziente[i] sono coprimi
2)n è coprimo con toziente[i] e con toziente[n-i]
3)toziente[i]+toziente[n-i]=n → x=toziente[i],y=toziente[n-i],n=k-1;
giusto giusto i constrains della equazione che dobbiamo risolvere e quante soluzioni
esistono contando pure il fatto che posso scambiare x e y esattamente toziente.size()
Hai ragione, non sono scritte chiaramente. Con “codivisore” intendevo indicare, dato d divisore di n, il divisore \frac{n}{d}. Il fatto che d|n \rightarrow \frac{n}{d}|n permette di cercare i divisori di n in O(\sqrt{n}) anziché in O(n); naturalmente occorre tenere presente che n = k^2 \rightarrow k = \frac{n}{k}.
Detto S_n = \left\{d \in \mathbb{N} \mathop{\big|} d|n \land d\geq 3\right\}, per ogni n \in \mathbb{N}-\{0\} il numero di soluzioni intere di a + b + \mathrm{gcd}(a, b) = n con a, b \geq 1 si può scrivere nella forma \sum_{d\in S_n}\varphi(d-1), dove \varphi è la funzione di Eulero.