This is a task from an old programming contest the task is as follows, A list of system of linear equations is given in the inputs.If the system is solvable we have to output the solution in the form of 'A + Bk',else we have to output "no solutions".
Now lets consider the inputs:
x = 3 (mod 4) x = 4 (mod 3) x = 1 (mod 2) x = 2 (mod 3) x = 3 (mod 4) x = 4 (mod 5) x = 5 (mod 6) x = 0 (mod 7) x = 2 (mod 2) x = 4 (mod 3) x = 6 (mod 5) x = 8 (mod 7) x = 10 (mod 11)
Using Chinese remainder theorem,I guess the outputs should be:
3 + 4k 1 + 3k 119 + 420k 736 + 2310k
But according to the Judges I/O the output is :
3 + 4k no solutions 119 + 420k no solutions
Now I can see many had solved this task could anybody explain how this output holds valid for the inputs?
PS:There is a note from the problem author that "Not all are solvable using the Chinese Remainder Theorem, and some aren't solvable at all!"