Программирование игр и головоломок

n = а*p + b²;

а — степень двойки,

p четно,

b нечетно, b < а.

Кроме того, мы знаем, что при выходе из цикла p < а.

Если p равно нулю, то n = b². Тогда мы видим, что n — квадрат числа b, которое выводится, и все закончено.

Но n может оказаться полным квадратом и тогда, когда p не нуль. Попробуем рассмотреть все возможные случаи. Положим n = r² (r нечетно). Соотношение

r² = ар + b дает

r²– b² = ар.

Положим r + b = 2u, r– b = 2v (r и b нечетны). Отсюда получаем 4uv = ар.

Поскольку r = u + v, где r нечетно, получаем, что u и v не могут быть числами одинаковой четности, так что одно из них четно, а другое нечетно. Так как а является степенью двойки, то нечетный сомножитель относится к p. Выявим его, полагая р = s2^t, где s нечетно, a t >= 1 (p четно).

Напомним, что а = 2^k. В этих обозначениях 4uv = ар = s2^k+t, uv = s2^{k+t– 2}.

Возможные решения для пары u, v имеют вид пар

s'2^{k+t– 2}, s''

где s's" = s.

Покажем сначала, что s" — меньший из этих двух элементов пары. Вследствие t >= 1 имеем k– t <= k + t– 2.

Вследствие p < а последовательно выводим

s2^t < 2^k,

s's"2^t < 2^k.

s's" < 2^{k– t} <= 2^{k+t– 2} <= s'²2^{k+t– 2}

(потому что s' нечетен и не меньше 1).

Следовательно, нужно взять u = s'2^{k+t– 2}, v = s".

Покажем теперь, что нужно обязательно взять s' =1, s" = s. По выбору u и v

b = 2^{k+t– 2}s' - s" < а = 2^k.

Отсюда получаем:

s" > 2^{k+t– 2}s' - 2^k,

и, так как t >= 1:

s" > 2^{k– 1}s' - 2^k,

s = s's" > 2^{k– 1}s'²– 2^ks = 2^{k– 1}s' (s' - 2).

Вследствие р = s2^t < а = 2^k выводим s < 2^{k– t} <= 2^{k– 1}.

Объединим два полученных неравенства:

2^{k– 1}s' (s' - 2) < x < 2^{k– 1}, поэтому s' (s' - 2) < 1.

Единственное нечетное число s', удовлетворяющее этому соотношению, это s' = 1. Следовательно, у нас остается единственная возможность:

u = 2^{k+t– 2}, v = s,

b = u– v = 2^{k+t– 2}– s < а = 2^k,

s > 2^{k+t– 2}– 2^k.

Так как s < 2^{k– t}, то t должно быть таким, чтобы

2^{k– t} > 2^{k+t– 2}– 2^k.

Поскольку t должно быть строго положительно, то его единственными возможными значениями являются t = 1 и t = 2.

При t = 1 имеем

p = 2s, b = 2^{k– t}– s = a/2 - p/2.

Следовательно, если 2b = а– p, то n — квадрат числа (а + p)/2 = а– b.