0
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – Hao Ye Aug 15 '14 at 15:10
  • $\begingroup$ @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) $\endgroup$ – user3923257 Aug 15 '14 at 15:13
  • $\begingroup$ ?? The ray from $(0,0,0)$ to $(1,2,0)$ will only go through lattice points of the form $(k, 2k, 0)$. $\endgroup$ – Hao Ye Aug 15 '14 at 15:16
  • $\begingroup$ what is an integral point? $\endgroup$ – RE60K Aug 15 '14 at 16:28
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.