(Время: 2 сек. Память: 16 Мб Баллы: 100) Совсем недавно Алиса начала проявлять нездоровый интерес к биномиальным коэффициентам, и каково было ее счастье, когда на день рождения ей подарили треугольник Паскаля! Теперь Алиса каждый день играет с ним и непременно узнает что-то новое о биномиальных коэффициентах, записанных в нем.
Но как это обычно и бывает со всеми игрушками, треугольник Паскаля ей очень скоро наскучил, и, решив, что ее уже ничем не удивить, Алиса выбросила его. Заметив это, Боб, старший брат Алисы, решил, что еще не все потеряно. Недолго думая, он сказал Алисе, что нашел огромное количество новых пар взаимно простых биномиальных коэффициентов, о которых она раньше и не догадывалась, и предложил ей сыграть в одну игру.
Он называет Алисе два целых неотрицательных числа n и k. В ответ Алиса должна назвать свою пару целых неотрицательных чисел m и t, такую что биномиальные коэффициенты C(n, k) и C(m, t) взаимно просты. Затем он спрашивает ее, какие еще взаимно простые с названным Бобом биномиальные коэффициенты она знает.
Боб выписал все названные Алисой биномиальные коэффициенты и собирается удивить ее, назвав еще один такой коэффициент C(p, l), что его нет среди выписанных Бобом коэффициентов и он был бы взаимно прост с названым им ранее.
Дополнительно, Боб решил найти наибольший общий делитель d биномиальных коэффициентов C(n, k) и C(m, t), чтобы проверить, не забыла ли Алиса то, чему научилась, играя с треугольником Паскаля сутками напролет. Помогите Бобу написать соответствующую программу.
Входные данные В первой строке входного файла INPUT.TXT записано четыре целых неотрицательных числа через пробел, не превышающих 500 000: k, n, t, m, причем k ≤ n, t ≤ m.
В следующей строке входного файла записано одно неотрицательное целое число q, не превышающее 500 000 – количество дополнительных биномиальных коэффициентов, которые назвала Алиса.
В последующих q строчках записаны пары из двух неотрицательных целых чисел ti и mi, разделенных пробелом, причем 0 ≤ ti ≤ mi ≤ 500 000.
Выходные данные В первую строку выходного файла OUTPUT.TXT необходимо вывести «Yes», если Алиса назвала взаимно простой с C(n, k) биномиальный коэффициент, и «No» иначе (слова должны быть выведены без кавычек). Если выведено «No», то в следующей строке должно быть записано целое число d – наибольший общий делитель биномиальных коэффициентов C(n, k) и C(m, t), взятый по простому модулю 109+9. И, наконец, в последней строчке должны быть записаны два целых неотрицательных числа l и p – параметры биномиального коэффициента C(p, l) соответственно, разделенные пробелом (0 ≤ l ≤ p ≤ 500 000). Если подходящих пар несколько, то выведите любую из них. Гарантируется, что для любых входных данных, удовлетворяющих условию, существует как минимум одна подходящая пара p и l.
Идей нет вообще, кто может подсказать, как решать данную задачу?