We are sum for we are many
Some Number
Это сложная версия задачи. Разница между простой и сложной версиями задачи заключается только в ограничении на \(t\). Вы можете делать взломы только в том случае, если обе версии задачи решены.
Вам даны два целых положительных числа \(l\) и \(r\).
Посчитайте количество уникальных троек целых чисел \((i, j, k)\) таких, что \(l \le i < j < k \le r\) и \(\operatorname{lcm}(i,j,k) \ge i + j + k\).
Здесь \(\operatorname{lcm}(i, j, k)\) означает наименьшее общее кратное (НОК) целых чисел \(i\), \(j\), и \(k\).
Выходные данные
Для каждого набора входных данных выведите единственное целое число — количество уникальных троек целых чисел, подходящих под условия задачи.
Примечание
В первом наборе входных данных существует \(3\) подходящих тройки:
- \((1,2,3)\),
- \((1,3,4)\),
- \((2,3,4)\).
Во втором наборе входных данных существует только \(1\) подходящая тройка:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 4
3 5
8 86
68 86
6 86868
|
3
1
78975
969
109229059713337
|