Это сложная версия задачи. Различия между двумя версиями выделены жирным шрифтом. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
У Shohag есть два целых числа \(x\) и \(m\). Помогите ему подсчитать количество целых чисел \(1 \le y \le m\) таких, что \(x \oplus y\) делится\(^{\text{∗}}\) либо на \(x\), либо на \(y\), либо сразу на оба числа. Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество подходящих \(y\).
Примечание
В первом наборе входных данных для \(x = 7\) существует \(3\) допустимых значения \(y\) среди целых чисел от \(1\) до \(m = 10\) — числа \(1\), \(7\) и \(9\).
- \(y = 1\) подходит, потому что \(x \oplus y = 7 \oplus 1 = 6\) и \(6\) делится на \(y = 1\).
- \(y = 7\) подходит, потому что \(x \oplus y = 7 \oplus 7 = 0\) и \(0\) делится как на \(x = 7\), так и на \(y = 7\).
- \(y = 9\) подходит, потому что \(x \oplus y = 7 \oplus 9 = 14\) и \(14\) делится на \(x = 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
7 10
2 3
6 4
1 6
4 1
|
3
2
2
6
1
|