Trovare triple che soddisfino l'equazione di modulo in $ o (n log n) $ tempo

Question

Dato $ n $, sto cercando di contare il numero di valori $ (a, b, c) $ che soddisfano la seguente equazione in $ o (n log n) $ tempo. Non ho bisogno dei valori stessi solo il numero di valori totali che soddisfano l'equazione

$$ a^2 + b^3 = c^4 mod n ,, $$

dove $ a, b, c in {0,1, ...., n-1 } $ e $ n $ è un numero naturale.

Qualcuno ha idea di come farlo? Ovviamente il controllo di tutti i valori produce $ o (n^2) $ tempo.

Sono in grado di calcolare le triple per un determinato valore di $ c $ entro il limite desiderato poiché puoi costruire un BST in $ O (n log n) $ tempo in cui le chiavi sono i valori del modulo particolari in $ b^3 $ E i valori sono il numero di istanze che compaiono. Quindi calcolando $ ((c^4 ! ! Mod n) + n - (a^2 ! ! Mod n)) ! ! Mod n $ per ogni valore di $ a $ e fare Una ricerca di quella chiave in $ b $ raggiungiamo il runtime desiderato.

Come posso ottenere lo stesso risultato per ogni valore di $ c $ anziché per uno specifico?

Presumo che il runtime $ o (n log n) $ provenga da una qualche forma di ricerca binaria, ordinamento o di ricerca binaria ma non sono sicuro esattamente come raggiungere questo obiettivo per tutti i valori di $ c $ piuttosto che uno specifico uno. Qualsiasi aiuto è apprezzato. Grazie.