Это сложная версия задачи. Различия между двумя версиями выделены жирным шрифтом. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
У Shohag есть два целых числа $$$x$$$ и $$$m$$$. Помогите ему подсчитать количество целых чисел $$$1 \le y \le m$$$ таких, что $$$x \oplus y$$$ делится$$$^{\text{∗}}$$$ либо на $$$x$$$, либо на $$$y$$$, либо сразу на оба числа. Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
$$$^{\text{∗}}$$$Число $$$a$$$ делится на число $$$b$$$, если существует целое число $$$c$$$ такое, что $$$a = b \cdot c$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая и единственная строка каждого набора входных данных содержит два целых числа $$$x$$$ и $$$m$$$ ($$$1 \le x \le 10^6$$$, $$$1 \le m \le 10^{18}$$$).
Гарантируется, что сумма $$$x$$$ по всем наборам входных данных не превосходит $$$10^7$$$.
Для каждого набора входных данных выведите одно целое число — количество подходящих $$$y$$$.
57 102 36 41 64 1
3 2 2 6 1
В первом наборе входных данных для $$$x = 7$$$ существует $$$3$$$ допустимых значения $$$y$$$ среди целых чисел от $$$1$$$ до $$$m = 10$$$ — числа $$$1$$$, $$$7$$$ и $$$9$$$.
Название |
---|