裴蜀定理

裴蜀定理内容：对于\(a,b\)是不为零的整数，存在\(x,y\)，使得\(ax+by=k*gcd(a,b)\)。

特别注意对于这个定理必须限制\(a,b,x,y\)为整数。

证明过程比较毒瘤，不过看看也是挺好理解的，可以自行上网。

裴蜀定理扩展

我们直接说常见的应用，基本上不会直接用原定理，一般都是用扩展多一些。

扩展到多项式

首先裴蜀定理可以扩展到多项式,比如洛谷上的模板题。

题目描述

给定一个包含 \(n\) 个元素的整数序列\(A\)，记作\(A1,A2,A3,...,An\)。

求另一个包含 \(n\)​ 个元素的待定整数序列 \(X\)​，记$ S=\sum_{i=1}^nA_i \times X_i$​​，使得 S>0 且 S 尽可能的小。

输入格式

第一行一个整数 \(n\)，表示序列元素个数。

第二行 \(n\) 个整数，表示序列 \(A\)。

输出格式

一行一个整数，表示 S>0 的前提下 S 的最小值。

输入输出样例

输入 #1

2
4059 -1782

输出 #1

99

说明/提示

对于 100%的数据，\(1≤n≤20,∣Ai∣≤10^5\),且 A 序列不全为 0。

裴蜀定理可以扩展到多项式所以$ S=\sum_{i=1}^nA_i \times X_i=gcd(A_i)\times k\(很显然因为\)S\(为\)A_i\(的公因数的倍数，所以当\)k=1\(时多项式最小，只需要一直枚举\)A_i\(取公因数​​即可，注意\)A_i$需要用绝对值。

#include<bits/stdc++.h>
using namespace std;
int n,ans;
inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main(){
	scanf("%d%d",&n,&ans);
	for(int i=2,x;i<=n;++i){scanf("%d",&x),ans=gcd(ans,abs(x));}
	printf("%d\n",ans);return 0;}

另外一种扩展

还是\(ax+by=n\),其中\(a,b\)互相为素数。

其中 x 和 y 为自然数。如果方程有解，称 n 可以被 a、b 表示。

记 \(C=ab-a-b\) 。由 a 与 b 互素，C 必然为奇数。则有结论：

对任意的整数 n，n 与\(C-n\)中有且仅有一个可以被表示。

即：可表示的数与不可表示的数在区间\([0,C]\) 对称（关于 C 的一半对称）。0 可被表示，C 不可被表示；负数不可被表示，大于 C 的数可被表示。

[NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目

很简单的一道结论题。

#include<bits/stdc++.h>
using namespace std;
long long a,b;

int main(){
    scanf("%lld%lld",&a,&b);
    printf("%lld\n",a*b-a-b);
    return 0;
}