洛谷P2520 裴蜀定理，多限制的不定方程解的构造

题意：

给出八个基底向量：
$(a, b), (- a, b), (a, - b), (- a, - b), (b, a), (- b, a), (b, - a), (- b, - a)$
问能否通过若干个上述向量相加得到相邻 $(x, y)$ ？

Solution：

显然我们只需加减以下四组基底相邻即可
$(a, b), (- a, b), (b, a), (- b, a)$
不妨设他们分别被算数增加了 $k_{i}$ 次， $k_{i}\in Z$ ，于是需要下列方程组有解
$k_{1}(a,b)+k_{2}(-a,b)+k_{3}(b,a)+k_{4}(-b,a)=(x,y)$
即

{\begin{cases} (k_{1} - k_{2}) a + (k_{3} - k_{4}) b = x \\ (k_{1} + k_{2}) a + (k_{3} + k_{4}) b = y \end{cases}

{(k_{1} - k_{2}) a + (k_{3} - k_{4}) b = x (k_{1} + k_{2}) a + (k_{3} + k_{4}) b = y

要方程组有解，这是两个不定方程，由裴蜀定理，首先需要

gcd(k_{1}-k_{2},k_{3}-k_{4})|x\\ gcd(k_{1}+k_{2},k_{3}+k_{4})|y

然后这样只保证了存在

k_{1}-k_{2}),(k_{1}+k_{2}),(k_{3}-k_{4}),(k_{3}+k_{4})

，我们的目的是使

k_{i}

有正整数解，此时我们可以这样解出

k_{1}

k_{1}=\frac{(k_{1}-k_{2})+(k_{1}+k_{2})}{2}

要使

k_{1}

是正整数，那么必须要分子为偶数，于是

k_{1}+k_{2})

与

k_{1}-k_{2})

奇偶性必须相同，同理对后两项也是的，接下来枚举他们的奇偶性：

若 $k_{1}-k_{2})$ 为偶数， $k_{3}-k_{4})$ 为偶数，那么方程组的 $(1)$ 式就可以写作
$2[(k_{1}-k_{2})a+(k_{3}-k_{4})b]=x\Rightarrow(k_{1}-k_{2})(2a)+(k_{3}-k_{4})(2b)=x$
此时只需要上述方程有解，就可以保证解出来的 $k_{1}-k_{2})$ 为偶数了，即只需要
$g c d (2 a, 2 b) ∣ x$
同理可得
$g c d (2 a, 2 b) ∣ y$
若 $k_{1}-k_{2})$ 为偶数， $k_{3}-k_{4})$ 为奇数，只需要左右两边 $+ b$ ，得到
$k_{1}-k_{2})a+(k_{3}-k_{4}+1)b=x+b$
这就转化为都是偶数的情形了，同上只需要
$g c d (2 a, 2 b) ∣ (x + b), g c d (2 a, 2 b) ∣ (y + a)$

下面两种情况同理，直接给出结论
若 $k_{1}-k_{2})$ 为奇数， $k_{3}-k_{4})$ 为偶数，只需要
$g c d (2 a, 2 b) ∣ (x + a), g c d (2 a, 2 b) ∣ (y + b)$
若 $k_{1}-k_{2})$ 为奇数， $k_{3}-k_{4})$ 为奇数，只需要
$g c d (2 a, 2 b) ∣ (x + a + b), g c d (2 a, 2 b) ∣ (y + a + b)$

上述四种情况满足一个即代表有解，并且上面每一种都包含最开始的裴蜀定理的条件，就无需再验证裴蜀定理了

// #include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=25,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=1e9+7;

template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}

ll tmp;

bool check(ll x,ll y){return x%tmp==0&&y%tmp==0;}

int main()
{
    #ifdef stdjudge
        freopen("in.txt","r",stdin);
    #endif
    int t; cin>>t;
    while(t--)
    {
        ll a,b,x,y; cin>>a>>b>>x>>y;
        tmp=gcd(a,b)<<1;
        if(check(x,y)||check(x+b,y+a)||check(x+a,y+b)||check(x+a+b,y+a+b)) printf("Y\n");
        else printf("N\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

相关阅读:
vue3父组件提交校验多个子组件
进度条——不仅仅是语言层面上的小程序
Python数字类型
菜鸟教程《Python 3 教程》笔记（19）：错误与异常
第十三章：IO流
快乐组队赛XD（2017 Chinese Multi-University Training, BeihangU Contest）
浅谈高速公路服务区分布式光伏并网发电
ceph操作
Java密码学之数字签名
Python深度学习-第一章、什么是深度学习

原文地址：https://blog.csdn.net/stdforces/article/details/127858235

洛谷P2520 裴蜀定理，多限制的不定方程解的构造

题意：

Solution：

下面两种情况同理，直接给出结论