题目链接:http://acm.nefu.edu.cn/JudgeOnline/problem/84.jsp
思路:与上一题很相似,扩展欧几里得算法。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> using namespace std; typedef long long LL; LL n, m, ax, by; void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y) { if(!b) { d = a; x = 1; y = 0; } else { ex_gcd(b, a%b, d, y, x); y -= x*(a/b); } } void read_case() { scanf("%lld%lld%lld%lld", &n, &m, &ax, &by); } void solve() { read_case(); LL d, x, y; ex_gcd(m, n, d, x, y); if((by-ax) % d) { printf("Impossible\n"); return ;} LL b1 = n / d; x *= (by-ax) / d; LL ans = (x % b1 + b1) % b1; printf("%lld\n", ans); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }