/* -*- coding: utf-8 -*- * * 2558.cc: No.2558 中国剰余定理 - yukicoder */ #include #include using namespace std; /* constant */ /* typedef */ /* global variables */ /* subroutines */ template void exgcd(T x, T y, T &a, T &b, T &c) { T r0 = x, r1 = y; T a0 = 1, a1 = 0; T b0 = 0, b1 = 1; while (r1 > 0) { T q1 = r0 / r1; T r2 = r0 % r1; T a2 = a0 - q1 * a1; T b2 = b0 - q1 * b1; r0 = r1, r1 = r2; a0 = a1, a1 = a2; b0 = b1, b1 = b2; } c = r0; a = a0; b = b0; } /* main */ int main() { int a, b, ra, rb; scanf("%d%d%d%d", &a, &b, &ra, &rb); int u, v, w; exgcd(a, b, u, v, w); //printf("%d * %d + %d * %d = %d\n", a, u, b, v, w); int x = ra * b * v + rb * a * u; while (x < 0) x += a * b; printf("%d\n", x); return 0; }