Пифагорын гурвал

Бодлогын дугаар: ABR0554

n натурал тоо өгөгдөв. Тус бүрийнх нь утга n-ээс хэтрэхгүй байх бүх натурал пифагорын гурвалыг буюу
a^2 + b^2 = c^2 ба
a ≤ b ≤ c ≤ n нөхцлүүдийг хангах бүх натурал тоон гурвалуудыг ол.

Энэ бодлогын хувьд өгүүлбэр, зорилго нь их энгийн хэрнээ хугацааны хувьд ярвигтай. Элдэв "дундын машин" ажилладаггүй Pascal, C/C++ гэх мэт дунд түвшний хэл дээр бодож Submit-лах нь тохиромжтой. Доор Python хэл дээрх эх кодыг нийтэллээ. Гэхдээ энэ кодыг шууд илгээхэд АС авахгүй шүү Python амжихгүй :P Алгоритмыг нь харж аваад for давталт ашиглаж Pascal, C/C++ дээр бичих нь тохиромжтой ;)

Алгоритмийн талаар тайлбар өгүүлэх нь:

Бодлогын өгөгдөл ёсоор
a ^ 2 + b ^ 2 = c ^ 2 үүнээс цаашлан задлаад
a ^ 2 = c ^ 2 - b ^ 2 = ( c - b ) * ( c + b ) = k гэе.

Одоо а тоог ямар нэг x , y тооны үржвэр хэлбэрээр тавигддаг гэж үзье / * тоог ямар ч тохиолдолд 2 тооны үржвэр хэлбэрт тавиж болно. Анхны тоо байх тохиолдолд ч a = a * 1 гэсэн үржвэр хэлбэрт тавьж болно * /.

a = x * y гэдгээс

k = x * ( x * y ^ 2) / * энэ тохиолдлыг эх код дээр
x = j, x * y ^ 2 = k / j гэж авсан байгаа.*/

( x * y ^ 2 + x ) % 2 == 0 байгаа үед

a ≤ b ≤ c ≤ n нөхцлийг хангах

b = ( x * y ^ 2 ) / 2
c = ( x * y ^ 2 + x ) / 2

болно. Баталгааг хийхээс бага зэрэг залхуурав.