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)$
↵
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)$
