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

Найти количество троек целых чисел (a, b, m) удовлетворяющих ограничениям amin £ a £ amax, bmin £ b £ bmax, mmin £ m £ mmax, для которых имеет место равенство

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

Вход. Первая строка содержит количество входных тестов T (1 £ T £ 20). Каждая из следующих T строк содержит 3 пары целых чисел amin, amax, bmin, bmax, mmin, mmax. Известно, что -1000 £ amin £ amax £ 1000, -1000 £ bmin £ bmax £ 1000, 1 £ mmin £ mmax £ 1000.

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

Пример входа

3

1 2 2 4 3 5

-100 100 200 350 1 1000

5 9 10 12 2 9

Пример выхода

Case 1: 6

Case 2: 318384

Case 3: 45

РЕШЕНИЕ

модулярная арифметика

Анализ алгоритма

Поскольку выражения a + b и a – b дают одинаковые остатки при делении на m, то их разница a + b – (a – b) = 2b делится на m. Задача свелась к поиску таких пар (b, m) из заданного интервала, для которых 2b делится на m.

Если m – нечетное, то b должно делиться на m. Количество таких b из интервала [bmin, bmax] равно

–

Если m – четное, то b должно делиться на m / 2. Количество таких b из того же интервала равно

–

Для каждого m Î [mmin, mmax] вычисляем и суммируем такое количество b. Поскольку для каждой пары (b, m), для которой 2b делится на m, любое a (количество возможных a равно amax – amin + 1) может образовать искомую тройку чисел (a, b, m), то найденное количество b следует умножить на (amax – amin + 1).

Пример

Рассмотрим первый тест, для которого 1 £ a £ 2, 2 £ b £ 4, 3 £ m £ 5. Переберем значения m:

m = 3 (нечетное). Имеется лишь одно b = 3, которое делится на m. Паре (b, m) = (3, 3) соответствуют решения

(1 + 3) mod 3 = (1 – 3) mod 3, (2 + 3) mod 3 = (2 – 3) mod 3

m = 4 (четное). Имеются два значения b, которые делятся на m / 2 = 2. Паре (b, m) = (2, 4) соответствуют решения

(1 + 2) mod 4 = (1 – 2) mod 4, (2 + 2) mod 4 = (2 – 2) mod 4

а паре (b, m) = (4, 4) решения

(1 + 4) mod 4 = (1 – 4) mod 4, (2 + 4) mod 4 = (2 – 4) mod 4

m = 5 (нечетное). В допустимом интервале для переменной не существует ни одного числа b, которое делится на 5. Поэтому для m = 5 решений нет.

Итого имеется 6 троек, удовлетворяющих первому тесту.

Реализация алгоритма

Обнуляем переменную res, в которой будет содержаться количество троек, удовлетворяющих условию задачи. Читаем входные данные.

res = 0;

scanf("%d %d %d %d %d %d",&amin,&amax,&bmin,&bmax,&mmin,&mmax);

Перебираем все возможные значения m, для каждого из них по формулам вычисляем количество таких b, для которых 2b делится на m.

for(m = mmin; m <= mmax; m++)

if (m % 2)

res += (int)floor(1.0*bmax/m) - (int)floor((1.0*bmin-1)/m);

else res += (int)(floor(2.0*bmax/m)) - (int)floor((2.0*bmin-2)/m);

Выражение (int)floor(1.0*bmax/m) нельзя переписать в виде bmax/m, так как при делении отрицательного числа на положительное округление компилятором C производится в большую сторону. А по условию задачи необходимо брать целую часть от числа (округление вниз). То есть при bmax < 0 приведенные выражения будут давать разные значения.

Умножаем res на amax – amin + 1 и печатаем результат:

res = res * (amax - amin + 1);

printf("Case %d: %d\n",i+1,res);