1980. Юстас-Алексу

После блестяще проведенной операции Штирлиц смог определить численность фашистской армии. Естественно такую информацию уже четыре года как ждут в штабе советской армии. Чтобы общаться со штабом Штирлиц использует n радистов. Каждый из радистов должен передать сообщение от Штирлица в штаб. Штирлиц, как хитрый разведчик, зашифровал свое послание таким образом: каждому из радистов он дал одно и то же число – численность армии, но в своей системе счисления, да еще так, что все основания систем счисления у радистов попарно взаимно простые. После передачи радиограммы ищейки Мюллера смогли определить последний символ каждого из сообщений. Вы работаете штатным программистом и должны определить, какое минимальное число мог послать Штирлиц в своем сообщении. Мюллер в отличие от вас не очень любит бинарный код, поэтому он хочет, чтобы искомое число вы вывели в десятичной системе.

Вход. В первой строке число n – количество радистов у Штирлица. В следующей строке n чисел a_i – основания систем счисления, в которых Штирлиц давал сообщения радистам (2 ≤ a_i ≤ 36). В третьей строке через пробел записано n символов c_i – последние буквы каждого из сообщений (0 ≤ c_i < a_i; c_i – либо цифра от 0 до 9, либо буква от A до Z).

Выход. В единственной строке вывести минимальное число, которое мог передать Штирлиц в десятичной системе.

Пример входа

2
6 13
1 B
 

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

37

РЕШЕНИЕ

теория чисел – китайская теорема про остатки

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

Пусть х – искомое минимальное число. Исходя из условия задачи, имеем следующую систему сравнений: , . Китайская теорему про остатки гласит, что поскольку все a_i взаимно простые, то система имеет единственное решение по модулю . Алгоритм Гаусса утверждает, что значение x вычисляется по формуле

x = mod a, где b_i = a / a_i, m_i = mod a_i.

Для вычисления обратного числа по модулю используется расширенный алгоритм Евклида.

Пример

Решим систему сравнений: . Имеем: a = 7 * 11 = 77, b₁ = 77 / 7 = 11, b₂ = 77 / 11 = 7, m₁ = (mod 7) = 11^-1 (mod 7) = 4^-1 (mod 7) = 2, m₂ = (mod 11) = 7^-1 (mod 11) = 8.

x = mod a = (3 * 11 * 2 + 5 * 7 * 8) mod 77 = (66 + 280) mod 77 = 346 mod 77 = 38.

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

Функция gcdext реализует расширенный алгоритм Евклида. По заданным n и m она находит такие g, t, u, что nt + mu = g, где g = НОД(n, m).

void gcdext(long long n,long long m, long long *g,

long long *t, long long *u);

Функция inv вычисляет a^-1mod p. Если ax + py = g, то ax mod p = g mod p. Если a и p взаимно простые, то g = НОД(a, p) = 1 и последнее равенство примет вид ax mod p = 1, откуда x = a^-1mod p. Значение x должно принадлежать интервалу от 0 до p – 1.

long long inv(long long a, long long p)

{

long long g, x, y;

gcdext(a,p,&g,&x,&y);

if (x < 0) x = p + x;

return x;

}

Рассмотрим дополнительные функции. Функция digit преобразовывает символ в цифру.

long long digit(char c)

{

if (c >= 'A') return c - 'A' + 10;

return c - '0';

}

Функция ToDecimal преобразовывает число в системе счисления base, заданное в строке s, в десятичное число.

long long ToDecimal(char *s, long long base)

{

long long i, res = 0;

for(i = 0; i < strlen(s); i++)

res = res * base + digit(s[i]);

return res;

}

Основная часть программы. Считываем входные данные, вычисляем произведение модулей в переменной a.

scanf("%lld",&n);

for(a = 1, i = 0; i < n; i++)

scanf("%lld",&ai[i]), a *= ai[i];

В массив c заносим последние буквы сообщений, преобразовывая их в числовое значение.

for(i = 0; i < n; i++)

scanf("%s",ch),c[i] = ToDecimal(ch,ai[i]);

При помощи алгоритма Гаусса находим минимальное число, которое мог передать Штирлиц.

for(res = i = 0; i < n; i++)

{

Bi = a / ai[i];

Mi = Bi % ai[i];

Mi = inv(Bi,ai[i]);

res = (res + c[i] * Bi * Mi) % a;

}

printf("%lld\n",res);