## IPSC 2007

## Solution to Problem R – Rasterized Lines

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 10^{14}. 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.