ACM模版
描述
题解
一看这道题我就知道是数论，也知道和欧几里得算法有关，但是再多的我就不知道了，因为根本不知道从哪儿推，无从下手的感觉，数论差真是心塞，网上找了份不错的代码，但是不是太懂其中推导过程。
如果有大神知道为什么这么写，烦请告知推导过程……十分、万分感谢！
代码
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b==
0)
{
x =
1;
y =
0;
return a;
}
ll ans = exgcd(b, a%b, x, y);
ll temp = x;
x = y;
y = temp - a/b*y;
return ans;
}
int main()
{
int K;
cin >> K;
ll X, Y, S, T;
while (K--)
{
scanf(
"%lld%lld%lld%lld", &X, &Y, &S, &T);
ll a, b;
ll g = exgcd(X, Y, a, b);
ll c = a * T / g;
ll d = b * T / g;
a *= S / g;
b *= S / g;
if (S % g ==
0 && T % g ==
0)
{
bool flag =
0;
for (
int i = -
2; i <=
2; i++)
{
ll x, y;
x = a + X / g * i;
y = b - Y / g * i;
for (
int j = -
2; j <=
2; j++)
{
ll x_, y_;
x_ = c + X / g * j;
y_ = d - Y / g * j;
if ((x + y_) %
2 ==
0 && (x_ + y) %
2 ==
0)
{
flag =
1;
break;
}
}
}
if (flag)
{
puts(
"Y");
}
else
{
puts(
"N");
}
}
else
{
puts(
"N");
}
}
return 0;
}
