# Counting points in/on cuboid

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 :

1. 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.

2. 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)

• In your example, aren't the constraints satisfied by shooting in the direction of any lattice point in the cuboid? (including $(1,2,0)$ and $(1,3,0)$ for example?) – Hao Ye Aug 15 '14 at 15:10
• @HaoYe Yeah But if you see they are covered in these 26 points by extending the lines joining (0,0,0) and (x,y,z) – user3923257 Aug 15 '14 at 15:13
• ?? The ray from $(0,0,0)$ to $(1,2,0)$ will only go through lattice points of the form $(k, 2k, 0)$. – Hao Ye Aug 15 '14 at 15:16
• what is an integral point? – RE60K Aug 15 '14 at 16:28

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)?