【题解】【P5656-【模板】二元一次不定方程(exgcd)】
离散小波变换°
2019-11-24 10:35:05
## 题目简述
$T(T\leq2 *10^5)$组数据,每组给出$a,b,c$,询问使得$ax+by=c$成立的解.$a,b,c\in[1,10^9]$
若有正整数解,输出:
- **正整数解**的个数
- **正整数解**中,最小的$x$与最小的$y$
- **正整数解**中,最大的$x$与最大的$y$
否则,若有整数解,输出:
- 所有**整数解**中 $x$ 的最小正整数值, $y$ 的最小正整数值
否则,输出$-1$.
---
## 题解
由**裴蜀定理**可知,$a,b$可以组成所有的$\gcd(a,b)$的倍数.因此,我们只需要判断$c$是否为$\gcd(a,b)$的倍数,即可判断是否有解.
如果有解我们可以用**扩展欧几里得算法**求出一组特解$x',y'$,使得$ax'+by'=\gcd(a,b)$.我们设$d=\gcd(a,b)$.
$\text{exgcd}($扩展欧几里得算法$)$详情可~~上百度~~[参考OI-WIKI](https://oi-wiki.org/math/gcd/),这里不再赘述.
我们需要求出使得$ax_0+by_0=c$的解.这时候,我们只需要将$a,b$分别乘上$\frac{c}{d}$即可获得$x_0,y_0$.**接下来的算法将会大量运用这组特解.**
虽然获得了一组解,但是他却$\text{too simple}$.这很显然对我们的解题帮助不大.因此我们需要变换一下$x_0,y_0$.
假设我们要将$x_0$扩大,即变成$x_0+p$.~~观察可得~~我们需要将$y_0$缩小,即$y_0$需要变成$y_0-q$.
$$\begin{cases}a*(x_0+p)+b*(y_0-q)=c\\a*x_0+b*y_0=c\end{cases}$$
解得$p=\frac{b*q}{a}$.我们需要获得尽可能小的**正整数**$p,q$.那么就有$a|b*q,b|b*q$.即$b*q$的最小值为$\text{lcm}(a,b)=\frac{a*b}{gcd(a,b)}$.得出:
$$\begin{cases}p_{min}=\frac{b}{d}\\q_{min}=\frac{a}{d}\end{cases}$$
### 下面是最关键的操作
我们需要将$x_0$调至最小正整数,同时改变$y_0$的值.
具体操作,就是我们求最小的$k$,使得$x_0+k*p\geq1$.移项,可得
$$k>\lceil\frac{1-x_0}{p}\rceil$$
接着,我们就可以$x_0+=p*k,y_0+=q*k$,来构造出一组船新的特解,使得$x_0$为**最小正整数**.
回到题目.~~这条题目要求是真™多~~
首先判断有解.然后判断$y_0$是否大于$0($因为我们已经保证了$x_0>0)$来处理是否有正整数解.
有整数解,那么我们要输出$5$个数字.让我们分别处理:
### 有正整数解
注:下述情况均为正整数解的情况.
1.**解的个数**.很显然,我们只需要不断将$y_0$减去$q$,同时$x_0$加上$p$即可构造出所有可行解.解的总个数为$\lfloor (y-1)/q\rfloor +1$
2.**$x$的最小正整数值**.这就是我们求出的$x_0$,输出即可.
3.**$y$的最小正整数值**.我们只需要将$y_0$不断减去$q($因为$x_0$最小时,$y_0$一定最大$)$,即答案为$(y-1)\%q+1$.需要特殊注意一下$0$的情况.
4.**$x$的最大正整数值**.我们需要将$x_0$加上尽可能多的$p$,也就是$y_0$要减去尽可能多的$q$.答案为$x+\lfloor(y-1)/q\rfloor*p$
5.**$y$的最大正整数值**.$x_0$为最小正整数时,$y_0$自然最大,输出即可.
### 无正整数解
1.**$x$的最小正整数值**,同上,当前的$x_0$即为最小的正整数值.
2.**$y$的最小正整数值**.很显然,当前$y_0\leq 0($不然就存在正整数解了$)$.我们需要执行构造$x_0$的方法,即$y_0+q*\lceil((1.0-y)/q)\rceil$
### 最后要注意的
1. 一定要开$\text{long long}$,不然会爆~~血的教训~~
2. 该题细节超多,比如上取整,下取整这些东西都要涉及一定类型转换
## 参考程序
```cpp
#include<bits/stdc++.h>
#define debug(x) printf("In function [%s],the value of ["#x"] is %d\n",__FUNCTION__,x)
#define up(l,r,i) for(register int i=l;i<=r;++i)
#define dn(r,l,i) for(register int i=r;i>=l;--i)
using namespace std;
typedef long long LL;
const int INF =2147483647;
int qread(){
int w=1,c,ret=0;
while((c=getchar())> '9'||c< '0')
w=(c=='-'?-1:1); ret=c-'0';
while((c=getchar())>='0'&&c<='9')
ret=ret*10+c-'0';
return ret*w;
}
void qwrite(int x){
if(x<0) x=-x,putchar('-');
if(x>9) qwrite(x/10);
putchar('0'+x%10);
}
LL exgcd(LL a,LL b,LL &x,LL &y){
LL d=a; if(b==0) x=1,y=0; else{
d=exgcd(b,a%b,y,x),y-=a/b*x;
}
return d;
}
int main(){
dn(qread(),1,T){
LL a=qread(),b=qread(),c=qread(),x,y;
LL d=exgcd(a,b,x,y);
if(c%d!=0) puts("-1"); else{
x*=c/d,y*=c/d; LL p=b/d,q=a/d,k;
if(x<0) k=ceil((1.0-x)/p),x+=p*k,y-=q*k; else //将x提高到最小正整数
if(x>=0)k=(x-1)/p ,x-=p*k,y+=q*k; //将x降低到最小正整数
if(y>0){ //有正整数解
printf("%lld ",(y-1)/q+1); //将y减到1的方案数即为解的个数
printf("%lld ",x); //当前的x即为最小正整数x
printf("%lld ",(y-1)%q+1); //将y取到最小正整数
printf("%lld ",x+(y-1)/q*p); //将x提升到最大
printf("%lld ",y); //特解即为y最大值
} else{ //无整数解
printf("%lld " ,x); //当前的x即为最小的正整数x
printf("%lld",y+q*(LL)ceil((1.0-y)/q)); //将y提高到正整数
}
puts("");
}
}
return 0;
}
```
---
$\rm upd 2020.3.21:$ 发现好像$\rm exgcd$并不需要满足$a>b$……已更改。