Q1: Let's first think for some interval of integers that we'll denote [x^2, (x+1)^2), how many valid pairs can we make? All numbers in this range would have the same hash.
There are ((x+1)^2 - x^2) = (2x+1) integers in this range. Thus, we have (2x+1)^2 total pairs in the range.
Now, we can count the pairs in ranges up to the largest x < floor(sqrt(k)), and the remaining pairs in the range (floor(sqrt(k))^2, k) can be counted in a similar fashion.