Given a cuboid that extend in x,y,z axis such that |x|≤N, |y|≤N, |z|≤N where N is given and can have value up to 10^9.Now a shooter is standing at origin (0,0,0).He need to shoot on any of the surfaces of the cuboid in such a way that these 2 conditions are satisified :
Their are atleast M integeral points (1≤M≤1000) on the line joining (0,0,0) and the point on surface (x,y,z) where shooter points.
Also count of these integral points should be divisble by given number D where 1≤D≤1000
Now we need to count the number of such lines along which the shooter can point his gun in such a way that these 2 conditions are satisified.
Example :
Let N=3 , M=2 and D=1 then here answer will be 26.
The directions in which shooter can point to satisfy these conditions are : (−1,−1,−1), (−1,−1,0), (−1,−1,1), (−1,0,−1), (−1,0,0), (−1,0,1) (−1,1,−1), (−1,1,0), (−1,1,1), (0,−1,−1), (0,−1,0), (0,−1,1) (0,0,−1), (0,0,1), (0,1,−1), (0,1,0), (0,1,1), (1,−1,−1) (1,−1,0), (1,−1,1), (1,0,−1), (1,0,0), (1,0,1), (1,1,−1) (1,1,0), (1,1,1)
HINT:
Suppose the shooter shoots at $(X,Y,Z)$, then the line joining this and origin will be $$ x=X/t,y=Y/t,z=Z/t;t>1$$ Suppose I take the point $(100,200,300)$ on a surface, then possible integral points are: $$(1,2,3),(2,4,6),(3,6,9),(4,8,12),...$$ So actually you have to select three mutually co-prime numbers and make multiples of them until you reach the border.Any ideas?
Now count of these point must be divisible by $D$. Any ideas (think in term of number of factors)?