Statement is not available in English language
D. НОД-свёртка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время урока математики в Ромашковой долине Крош увлечённо изучал свойство векторов: $$$$$$ \overrightarrow{AB} + \overrightarrow{BC} = \overrightarrow{AC}. $$$$$$ Вдохновившись этой идеей сложения «по цепочке», он задумался: а можно ли придумать похожее правило для чисел с использованием наибольшего общего делителя?

Крош назвал тройку целых неотрицательных чисел $$$(A, B, C)$$$ НОД-свёртываемой, если выполняется равенство $$$$$$ \gcd(A + B,\; B + C) = A + C, $$$$$$ где $$$\gcd(x, y)$$$ — наибольший общий делитель неотрицательных целых чисел $$$x$$$ и $$$y$$$ (по соглашению, $$$\gcd(x, 0) = x$$$ при $$$x \ge 0$$$).

Пин, как истинный учёный, предложил проверить гипотезу на диапазонах значений: $$$$$$ L_A \le A \le R_A,\quad L_B \le B \le R_B,\quad L_C \le C \le R_C. $$$$$$

Помогите Смешарикам определить, сколько существует НОД-свёртываемых троек в заданных пределах.

Входные данные

В первой строке заданы два целых числа $$$L_A$$$ и $$$R_A$$$ ($$$0 \le L_A \le R_A \le 10^9$$$) — границы для $$$A$$$.

Во второй строке — два целых числа $$$L_B$$$ и $$$R_B$$$ ($$$0 \le L_B \le R_B \le 10^9$$$) — границы для $$$B$$$.

В третьей строке — два целых числа $$$L_C$$$ и $$$R_C$$$ ($$$0 \le L_C \le R_C \le 10^9$$$) — границы для $$$C$$$.

Длины всех трёх диапазонов не превосходят $$$300\, 000$$$.

Выходные данные

Выведите одно целое число — количество НОД-свёртываемых троек $$$(A, B, C)$$$, удовлетворяющих ограничениям. Гарантируется, что ответ не превышает $$$2 \cdot 10^9$$$.

Система оценки

В данной задаче $$$3$$$ группы тестов, не считая примеров. Обозначим $$$\max(R_A - L_A, R_B - L_B, R_C - L_C)$$$ за $$$D$$$.

ПодзадачаБаллыОграничения $$$D$$$Необходимые подзадачиДоп. ограничения
110$$$D \le 100$$$—$$$L_A \ge 1,\ L_B \ge 1,\ L_C \ge 1$$$
210$$$D \le 100$$$——
360$$$D \le 300\, 000$$$1$$$L_A \ge 1,\ L_B \ge 1,\ L_C \ge 1$$$
420$$$D \le 300\, 000$$$1–3—
Примеры
Входные данные
1 1
2 2
3 3
Выходные данные
0
Входные данные
1 1
1 2
1 1
Выходные данные
1
Входные данные
1 10
5 12
3 7
Выходные данные
3
Входные данные
0 1
1 2
1 1
Выходные данные
3
Примечание

В первом примере единственная тройка, которая удовлетворяет трём неравенствам, — это $$$A = 1,\ B = 2,\ C = 3$$$. Однако $$$\gcd(A+B,B+C) =\gcd(3,5) = 1,\ A+C = 4$$$, а значит тройка не подходит.

Во втором примере возможны две тройки: $$$A = B = C = 1$$$ и $$$A = 1,\ B = 2,\ C = 1$$$. Для первой тройки $$$\gcd(A + B,B + C) = \gcd(2,2) = 2, \ A+C = 2$$$ — тройка подходит. Для второй тройки $$$\gcd(A + B,B + C) = \gcd(3,3) = 3, \ A+C = 2$$$, $$$3 \ne 2$$$ — тройка не подходит.