Тавил:
Өгөгдсөн N (1 <= N <=100000) тоог хамгийн цөөндөө хичнээн тооны квадратуудын нийлбэрт тавьж болох вэ?
[Эх өгүүлбэр]
Бодолт:
Ямар ч натурал тоог 4 бүхэл тооны квадратуудын нийлбэр хэлбэрт тавигддаг гэсэн теоремын дүгнэлтийг шууд авч ашиглавал бидний гаргах ёстой хариулт маань 1, 2, 3, 4 гэсэн 4 утгын нэг байх юм.
N <= 100000 гэдгийг анхаарвал хариулт нь 1 байх тоонуудыг ойролцоогоор 320 удаагийн үйлдлээр (1х1, 2х2, 3х3, ... , 320х320), хариулт нь 2 байх тоонуудыг 320х320 удаагийн үйлдлээр, хариулт нь 3 байх тоонуудыг 320х320х320 (1 секундэд амжиж байна лээ :D) удаагийн үйлдлээр бүгдийг нь бүртгээд массивт хадгалчихаж болно. Харин массивын утга нь 0 байгаа тоонууд нь хамгийн цөөндөө 4 квадрат тооны нийлбэрт тавигдах тоонууд болж таарах юм.
Гоё санаа байна баярлалаа. Хариултыг хайдаг зайлшгүй рекурс ашигладаг бодлого байвал тайлбарлаж өгөөч.
ReplyDelete