e-olymp
Yarışlar

ДЛКШ-2011 Теория чисел. Избранное

Модулярные уравнения

Законы модулярной арифметики являются лучшим оружием в нашем арсенале. Мы, подражатели ученых, часто используем эти законы для управления миром. Например, если мы хотим вычислить

23513714 - 24514732

то это можно сделать в один миг. Однако для этого следует решить уравнения в модулярной арифметике, и многие из нас могут прийти в замешательство. Но не бойтесь; мы не будем устрашать Вас ужасной системой модулярных уравнений, мы дадим Вам простую задачку. По заданным интервалам трех целых чисел a (aminaamax), b (bminbbmax) и m (mminmmmax) Вам следует найти количество таких троек (a, b, m), которые удовлетворяют уравнению:

(a + b) mod m = (a - b) mod m

Рассмотрим пример.

1a2, 2b4, 3 m5

(1 + 2) mod 4 = 3 = (1 - 2) mod 4

(1 + 3) mod 3 = 1 = (1 - 3) mod 3

(1 + 4) mod 4 = 1 = (1 - 4) mod 4

(2 + 2) mod 4 = 0 = (2 - 2) mod 4

(2 + 3) mod 3 = 2 = (2 - 3) mod 3

(2 + 4) mod 4 = 2 = (2 - 4) mod 4

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

Первая строка содержит количество тестов t (1t20). Каждая из следующих t строк является отдельным тестом и содержит три пары целых чисел amin, amax, bmin, bmax и mmin, mmax. Известно, что -1000aminamax1000, -1000bminbmax1000, 1mminmmax1000.

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

Для каждого теста вывести в отдельной строке его номер и количество троек (a, b, m), удовлетворяющих модулярному уравнению.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
1 2 2 4 3 5
-100 100 200 350 1 1000
5 9 10 12 2 9
Çıxış verilənləri #1
Case 1: 6
Case 2: 318384
Case 3: 45