Матч 430, Битовые уравнения (BitwiseEquations)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Заданы два положительных целых числа x и k. Решить уравнение

x + y = x | y

и вернуть его k - ое наименьшее положительное целое решение (индекс k начинается с 1). Оператор | обозначает ‘OR’.

Класс: BitwiseEquations

Метод: long long kthPlusOrSolution(int x, int k)

Ограничения: 1 £ x, k £ 2*10⁹.

Вход. Два положительных целых числа x и k.

Выход. k - ое наименьшее положительное целое решение приведенного в условии уравнения.

Пример входа

x	k
5	1
5	5
10	3

Пример выхода

2

18

5

РЕШЕНИЕ

математика

Значение y будет решением уравнения тогда и только тогда, когда y имеет нули в тех позициях, в которых в x стоят единицы. Например, если x = 1001101001₂ = 617₁₀, то последние 10 цифр y должны быть 0**00*0**0, где ‘*’ обозначает 0 или 1. Любая замена звездочек на 0 или 1 дает решение. Наименьшим будет решение, когда звездочки будут заменены на 00001, то есть y = 0000000010 = 10₂ = 2₁₀, x + y = x | y = 1001101011₂ = 619₁₀. Второе наименьшее решение получится, если звездочки заменить на 00010, третье – если на 00011 и так далее.

k - ое наименьшее положительное целое решение уравнения можно получить, если звездочки заменить на двоичное представление числа k.

ПРОГРАММА

#include <stdio.h>

class BitwiseEquations

{

public:

long long kthPlusOrSolution(long long x, long long k)

{

long long pos, res = 0;

for(pos = 0; k; pos++)

{

if (x >> pos & 1) continue;

if (k % 2) res = res | (1LL << pos);

k/=2;

}

return res;

}

};