# 拓展欧几里得 随便写的，试试水 常用于求 $ax+by=\gcd(a,b)$ 的一组可行解 或求解 $ax+by=m$ 的解，当 $m|\gcd(a,b)$ 时原方程有整数解为上式的解乘 $\frac{m}{\gcd(a,b)}$ 对于模线性方程 $ax≡b (mod n)$ 可以化简为 $ax + ny = b$，设 $d = gcd(a, n)$ 当且仅当 $b % d == 0$ 时有解，且有d个解 [模板](https://www.luogu.com.cn/problem/P5656 "模板") ```c++ #include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' ll exgcd(ll a,ll b,ll &x,ll &y){ if(!b){x=1,y=0;return a;} ll d=exgcd(b,a%b,x,y); ll t=x;x=y,y=t-(a/b)*y; return d; } ll a,b,c,x,y; void solve(){ cin>>a>>b>>c; ll d=exgcd(a,b,x,y);//返回gcd(a,b) if(c%d==0){ 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;//x提到最小正整数 else k=(x-1)/p,x-=p*k,y+=q*k;//x降到最小正整数 if(y>0){//有正整数解组 cout<<(y-1)/q+1<<" ";//解个数 cout<<x<<" ";//最小正整x cout<<(y-1)%q+1<<" ";//最小正整y cout<<x+(y-1)/q*p<<" ";//最大正整x cout<<y<<endl;//最大正整y }else{ cout<<x<<" ";//最小正整x cout<<y+q*(ll)ceil((1.0-y)/q)<<endl;//最小正整y } }else cout<<-1<<endl;//无解 } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T; cin>>T; while(T--) solve(); } ``` 由特解求通解 $x'=x_0+k*\frac{b}{\gcd(a,b)}$ $y'=y_0-k*\frac{a}{\gcd(a,b)}$ # 裴蜀定理 设 $a$,$b$ 是不全为零的整数，则存在整数 $x$,$y$, 使得 $ax+by=\gcd(a,b)$ >推论 设自然数 a、b 和整数 n。a 与 b 互素。考察不定方程：$ax+by=n$ 其中 x 和 y 为自然数。如果方程有解，称 n 可以被 a、b 表示。 记 $C=ab-a-b$。由 a 与 b 互素，C 必然为奇数。则有结论： 对任意的整数 n，n 与 C-n 中有且仅有一个可以被表示。 即：可表示的数与不可表示的数在区间 [0,C] 对称（关于 C 的一半对称）。0 可被表示，C 不可被表示；负数不可被表示，大于 C 的数可被表示。 --- >noip2017 小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？ ans=ab-a-b --- >NOIP2005 过河 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L（1<=L<=1e9），青蛙跳跃的距离范围S,T<=10，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 路径压缩 假设每次走p或者p+1步.我们知道 $\gcd(p,p+1)=1$ 我们需要求得一个最小的值tt使得对于所有$s>t$ 的 $px+(p+1)y=spx+(p+1)y=s$一定有非负整数解。根据NOIP2017提高组D1T1的结论，我们可以知道这个数为 $t=p(p+1)-p-(p+1)t=p(p+1)−p−(p+1)$。由于本题的最大步长为10，因此 $t_{max}=9\times10-9-10=71$ 但是要注意，对于 $s=t$ 这种特殊情况，这种方法是不成立的应为在这种情况下，每次是不能够走p+1步的，因此需要另外特殊判断。 而且有可能跳过终点,所以dp的时候要循环到L+t-1 a,b不互质时不便压缩,因为必须有 $s|\gcd(a,b)$ ---