Простых чисел до sqrt(N) меньше 10000, поэтому найти разложение заданных чисел в простые можно за менее 100 миллионов операций.

Заметим, что нам не важно, какие именно простые входят в данное число, важно лишь количество каждого отдельно взятого простого. Возьмём все такие количества и сложим их в вектор, который отсортируем по неубыванию. Будем использовать динамику с запоминанием ответов для таких векторов. Тогда для каждого вектора мы посчитаем описанную Вами prob[i] всего один раз. Уникальных векторов, в отличие от чисел, не очень много, поэтому все 10000 тестов проходятся очень быстро, потому что для одних тестов используются запомненные значения из других.

Код: http://ideone.com/gJXUtq

Задачу A все решают рандомом. Пока есть время, то всем переменным присваиваем значения случайным образом, затем находим значения выражений. Если они не равны, то выводим нолик. Если время подходит к концу, то выводи единичку.
Мне кажется, что тесты очень-очень слабые, так как на таком тесте

a ^ b ^ c ^ d ^ e ^ f ^ g ^ h ^ i ^ j ^ k ^ l ^ m ^ n ^ o ^ p ^ q ^ r ^ s ^ t ^ u ^ v ^ w ^ x ^ y ^ z ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ L ^ M ^ N ^ O ^ P ^ Q ^ R ^ S ^ T ^ U ^ W ^ X ^ Y ^ Z
a ^ b ^ c ^ d ^ e ^ f ^ g ^ h ^ i ^ j ^ k ^ l ^ m ^ n ^ o ^ p ^ q ^ r ^ s ^ t ^ u ^ v ^ w ^ x ^ y ^ z ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ L ^ M ^ N ^ O ^ P ^ Q ^ R ^ S ^ T ^ U ^ W ^ X ^ Y ^ ~ Z

любой рандом выведет 1, хотя есть набор пременных (1111..111 или 1111..110) при которых уравнения не равны. Всего 2^51 вариантов, угадать 2 из 2^51 — без шансов. =)

SEERC в тренировки на codeforces добавил Temirulan, так что спроси у него, кто авторы задач =)

Не сразу понял о чём вы. Даже не заметил этого.) Видимо авторы забыли добавить задачу в треньку =)

Официальные тесты этой задачи видимо некорректны. На все тесты у них один ответ: eroare deschidere fisier 0

Корни нашего полинома могут быть целыми, рациональными (дробь) или иррациональными.
Рациональных корней не будет, так как самый первый коэффициент равен 1.
Док-во тут
Итак, перебираем 21 возможных целых корней (от -10 до 10). Учитываем сколько раз он встретился. Для этого делим наш полином на (x-v) до тех пор, пока делится "без остатка", где v — это корень. (Или же юзаем схему Горнера) Ответ на задачу: N — количество_целых_корней.

Да, у румынских авторов интересное чувство юмора. Они часто пытаются развеселить участников подобным образом, это уже не первый год) Со временем к таким вещам начинаешь привыкать...

Вики говорит, что задача нехорошая, да.

А также ещё шутки: в задаче говорится, что в строке не более 51 переменной (это логично 26 строчных + 25 заглавных), но нигде не написано про длину выражения. Может там такой есть тест: (((...(A ^ B)...))), где количество скобок ~1e6 штук. =) Например в 3 тесте длина выражения без пробелов ~600 символов, суммарное количество переменных (с повторами) ~160.