Задача была на командной олимпиаде на сайте acmp.ru Я пробовала решить её во время соревнования, но всегда получала TLE. Сама задача мне очень понравилась :) Было бы интересно послушать ваши идеи по поводу её решения.
в целом, суть задачи такова:
даны 6 чисел: a,b,c,d,e,f (a,b,c,d,e,f<=10^9). Требуется вывести 'YES', если существует такое число N, что
a*n mod c=b и d*n mod f=e.
Иначе вывести 'NO'.
Заранее спасибо :)
дам идею: можно решить каждое из двух модульных уравнений a*n = b (mod c) и d*n = e (mod f) (естественно заодно проверяя наличие решений в них), а потом составить диофантово уравнение и проверить его на наличие корней. http://e-maxx.ru/algo/diofant_1_equation
Имеем систему сравнений:
Если
или 
, то одно из сравнений неразрешимо, выведем 'NO'. Иначе, решим каждое из двух сравнений:
где
, 
. Пусть n = c1t1 + n1, тогда из второго сравнения следует, что должно выполняться 
. Аналогично проверим разрешимость полученного сравнения, т.е. условие 
. Если неразрешимо, выведем 'NO', иначе ответ 'YES', т.к. подставляя t1 в n = c1t1 + n1 получим решение исходной системы, т.е. решение существует.
nevermind
вроде теховские вставки нельзя править, если они корректно распознались