Imagine that there is a line from (0, 0) to (n, m) for some fixed n and m. If we draw it in left-to-right direction we can see this − the line leaves each square either at the right side (a), at the upper-right corner (b) or at the top side (c). With event of type (a) the integer part of the x-coordinate of the line increases by one, with type (c) the integer part of the y-coordinate increases by one. Finally with event of type (b) both integer parts increase by one. (We do not count point (0, 0) as event (b), but we count (n, m).)
Let A is the number of events of type (a), B of type (b) and C of type (c). We know that (n, m)=(1, 0)*A+(1, 1)*B+(0, 1)*C or in other words n=A+B, m=B+C. The number of black pixels is A+B+C. We know numbers n and m and if we could calculate number B, we could also calculate how many dark pixels will make the line to (n, m). Now we will prove that B=gcd(n, m) (GCD stands for greatest common divisor). Imagine that there is an event of type (b) at (x, y). We know that y=x*m/n and y*n=x*m (0<y<m, 0<x<n). This equation has exactly gcd(n, m)-1 solutions (this is left as an exercise to the reader).
Thus the number of black pixels for the line from (0, 0) to (n, m) is A+B+C+1=n-B+B+m-B=n+m-gcd(n, m). Let the number in the input is K. We have to find the number of solutions of the equation K=n+m-gcd(n, m) and we know that n and m are positive. We can write n and m as follows: n=u*gcd(n, m), m=v*gcd(n, m). That implies K=gcd(n, m)*(u+v-1). So K has to be divisible by gcd(n, m). The problem statement says that K has at most 47 divisors. So we can take every divisor of K and use it as gcd(n, m). Let d=gcd(n, m), K=w*d, w*d=d*(u+v-1), w=u+v-1, w+1=u+v. We know that u and v are relatively prime and they are both positive and less than w. That implies that the number of solutions of this equation is φ(w+1) (φ is Euler's totient function).
And now for the algorithm: at first we generate all primes less than 10 000 000, because input numbers are less than 1014. This can be done very fast with Eratosthenes sieve. Then we factorize the number K from the input and iterate through the divisors. We sum together numbers φ(K/d+1) for all divisors d of K. Euler's function can be computed as fast as we can factorize a number.