Форум Всеукраїнської інтернет-олімпіади NetOI

Коротко: бінарний пошук за відповіддю, частковий випадок принципу включень та виключень

Спочатку навчимося розв’язувати таку задачу: дане число M, яке гарантовано належить послідовності №k; знайти номер цього числа в цій послідовності. Легко бачити, що тут відповіддю буде просто корінь k-ої степені з M.

Потім трохи узагальнимо попередню задачу: дано число M, яке можливо належить послідовності №k, а можливо й ні; сказати, яке найближче знизу (тобто максимальне серед усіх чисел i<=M) число є елементом k-ої послідовності, і його номер у цій послідовності. Тут теж рахуємо корінь k-ої степені з M, але потім його ще приводимо до цілого (вниз, інакше кажучи floor), і рахуємо степінь від (приведеного до цілого) кореня.

Тепер, коли ми навчилися знаходити номер у послідовності за значенням, можна перейти до знаходження за значенням номера у об’єднанні послідовностей. Тут слід міркувати за принципом включень та виключень: знайти кількість менших-рівних елементів у одній послідовності, кількість менших-рівних елементів у іншій, і відняти кількість менших-рівних елементів, які належать обом послідовностям одночасно. Оскільки послідовності мають сАме вказаний вигляд, то одночасно обом послідовностям №a та №b будуть належати в точності елементи 1^(НСК(a,b)), 2^(НСК(a,b)), 3^(НСК(a,b)), ..., j^(НСК(a,b)), ..., де НСК(a,b) -- найменше спільне кратне.

Зробивши a>=b (тобто, обмінявши їх у разі потреби місцями), можна стверджувати, що остаточна відповідь задачі буде в межах між (n/2)^b до n^b. Ну і в цьому проміжку цілком можна робити звичайний бінарний пошук: спочатку left=(n/2)^b, right=n^b, потім багатократно брати середнє значення mid=left+(right-left)/2 і перевіряти номер у об’єднанні послідовностей значення, найближчого знизу до mid, залежно від результату міняти left чи right, і так далі.

Зверніть увагу, що при дуже великих, на межі діапазону типу, але гарантовано додатних значеннях, left+(right-left)/2 реально краще, ніж більш класичне (left+right)/2.

Відзначимо, що видобувати корені з точністю типа double недостатньо, а точності long double (extended) нібито достатньо. Але заради гарантованої правильності цілком можна вжити якісь додаткові перевірки, наприклад, спочатку заокруглити корінь догори, а потім зменшувати, поки степінь цього кореня (яку можна рахувати точно) не стане меншою-рівною M. Ну і само собою, що для точного подання чисел до 10^19 треба використовувати не просто 64-бітовий тип, а обов’язково 64-бітовий беззнаковий (QWord, unsigned long long).

Відредаговано Ilya Porublyov (2013-02-17 18:24:54)