Question about problem 233 — B. Non-square Equation
Difference between en3 and en4, changed 2 character(s)
Hello,  ↵

In problem: [problem:233B]  ↵
I was wondering why in submissions like this [submission:12604154] it is sufficient to only check a small range around the square root of n. How can I deduct something like this from the equation, and how to prove it?  ↵

Thanks.  ↵

Update: Here's a formulation that helped me understand it, maybe it'll be useful for someone.  ↵

The main equation is: $X^2 + X * S(X) = N$  ↵

Let $Y = X + S(X)$.   ↵
$Y^2 = X^2 + 2 * X * S(X) + {
(S(X))}^2$     $Thus$    ↵
$Y^2 >= X^2 + X * S(X)$  ↵

Since $X^2 + X * S(X) = N$ then  ↵
$Y^2 >= N$  ↵
${(X + S(X))}^2 >= N$  ↵
$X + S(X) >= sqrt(N)$  ↵

$X >= sqrt(N) - S(X)$

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Bekh 2019-06-12 23:55:08 102
en4 English Bekh 2019-06-09 08:50:34 2 Tiny change: '* S(X) + {S(X)}^2$ ' -> '* S(X) + {(S(X))}^2$ '
en3 English Bekh 2019-06-09 08:49:07 382 Tiny change: ' S(X) = N$, or $X + S(X)' -> ' S(X) = N$ $OR$ $X + S(X)'
en2 English Bekh 2019-06-09 06:14:45 30 Tiny change: 'lo, \n\nI was wo' -> 'lo, \n\nIn problem: [problem:233B]\nI was wo'
en1 English Bekh 2019-06-09 06:13:48 293 Initial revision (published)