Yes if x^a mod b = c then (x+b)^a mod b = c. So there would be a total of 1 + floor((u-x)/b) solutions thus far. You just have to remember to skip those numbers while you are searching for other solutions from (x+1) to min(u,b).
The concept works for 2 variables but much more computationally intensive. You solve x^a mod b = d and save the count as T[d] where 0 ≤ d < b. You might ask why 0 ≤ d < b and not 0 ≤ d ≤ c. This example is why: if c=7 and b=35 then (x,y) such that x^a mod 35 = 8 and y^a mod 35 = -1 ≡ 34 would be a solution as well.
Then the total number of solutions is similar to what you suggested except I don't bother with separate handling of x=y and x≠y:
for (i=0 ; i < b ; i++)
count += T[i]*T[(b +c -i)%b];