ACROSS:
A. a square
C. a multiple of N Across
E. (C Down) $\times$ (I Across)
G. a square root of A Down
I. a square root of D Down
J. (J Across) $\times$ (K Across) = (F Down) $\times$ (M Down)
K. (J Across) $\times$ (K Across) = (F Down) $\times$ (M Down)
L. a divisor of H Down
N. a divisor of O Down
P. a divisor of I Down
R. a multiple of P Down
S. a square of Q Down
DOWN:
A. a square of G Across
B. a square
C. not a square
D. $1000-$(A Across)
F. a power
H. (L Across) $\times$ (N Across)
I. a multiple of P Across
L. (P Down) $\times$ (Q Down)
M. a power
O. a multiple of N Across
P. a divisor of R Across
Q. a square root of S Across
Edit:
No numbers begin with digit 0 and all numbers are different. So the correct answer should contain twelve distinct 2-digit numbers and twelve distinct 3-digit numbers.