2924. 线性同余方程
SPJ
时间限制：1000 MS 内存限制：128 MB
题目描述
# 线性同余方程 ## 题目描述 给定 $n$ 组数据，每组数据包含三个整数 $a_i,b_i,m_i$。 对于每组数据，请求出一个整数 $x_i$，使其满足线性同余方程： $$ a_i x_i \equiv b_i \pmod{m_i}. $$ 即 $a_i x_i-b_i$ 能被 $m_i$ 整除。如果不存在这样的整数，则输出 `impossible`。 ## 输入格式 从文件 `congruence.in` 中读入数据。 第一行包含一个整数 $n$，表示数据组数。 接下来 $n$ 行，每行包含三个整数 $a_i,b_i,m_i$，表示一组数据。 ## 输出格式 将结果输出到文件 `congruence.out` 中。 输出共 $n$ 行，第 $i$ 行对应第 $i$ 组数据： - 如果有解，输出一个满足同余方程的整数 $x_i$。 - 如果无解，输出 `impossible`。 答案可能不唯一，输出任意一个满足条件且在 $32$ 位有符号整数（`int`）范围内的解均可，即： $$ -2^{31}\le x_i\le 2^{31}-1. $$ ## 数据范围 - $1\le n\le 10^5$。 - $1\le a_i,b_i,m_i\le 2\times 10^9$。 ## 样例输入 ``` 2 2 3 6 4 3 5 ``` ## 样例输出 ``` impossible -3 ``` ## 样例说明 第一组数据中，$2x-3$ 为奇数，不可能被 $6$ 整除，因此无解。 第二组数据中，取 $x=-3$，则 $4\times(-3)-3=-15$ 能被 $5$ 整除，因此 $-3$ 是一个合法解。 ## 运行限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$128$ MB。