扩欧的基础：https://blog.csdn.net/m0_37579232/article/details/81428065
在这里就总结一下求通解、最小正整数解
int extgcd(int a,int b,int& x,int& y){//返回值是a，b的最大公约数 int d=a;if(b!=0){d=extgcd(b,a%b,y,x);y-=(a/b)*x;}else{x=1;y=0;}return d;}扩欧求出来的解x，y是方程：ax+by=gcd(a,b)的解
x0=x*c/gcd
y0=y*c/gcd
x0,y0是方程ax+by=c的解
那么怎么求方程ax+by=c的通解呢？
让x0向左、右平移n格，y的变化（n为整数）
y0=(c-a*x0)/b
y1=(c-a*x1)/b=(c-a*(x0+n))/b=y0-a/b*n
也就是说x1=x0+n；y1=y0-a/b*n
把a/b转换为整数：
x1=x0+b*n
y1=y0-a*n
这样是不是就得到通解了？再想想，x每次变化b个单位真的能得到通解吗？
b/=gcd(a,b)
a/=gcd(a,b)
这样就好啦，因为把a，b化到最小，使得n前的系数最小，可得更多的解
int x,y,kx,ky;int gcd=extgcd(a,b,x,y);x*=c/gcd;y*=c/gcd;kx=b/gcd;ky=-a/gcd;//通解就是：x+kx*n,y+ky*n得到通解后，怎么求最小正整数解呢？
已知：x+b/gcd*n是x的通解（相当于x每次可以增减：b/gcd的整数倍）
最小正整数解就是x=(x+b/gcd*n)%(b/gcd)=x%(b/gcd)
若x<=0，则x+=b/gcd
int x,y;int g=extgcd(a,b,x,y);x*=c/g;b/=g;if(b<0)b=-b;int ans=x%b;if(ans<0)ans+=b;板子题：
poj2115
代码如下：
#include<iostream>#include<cstdio>#include<algorithm>#include<string>#include<cstring>#include<queue>#include<stack>#include<cmath>#include<set>#include<map>using namespace std;#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef pair<int,int>P;const int INF=0x3f3f3f3f;ll extgcd(ll a,ll b,ll& x,ll& y){//返回值是a，b的最大公约数ll d=a;if(b!=0){d=extgcd(b,a%b,y,x);y-=(a/b)*x;}else{x=1;y=0;}return d;}int main(){ ll A,B,C,K; while(scanf("%lld%lld%lld%lld",&A,&B,&C,&K)){ if(A==0&&B==0&&C==0&&K==0)break; ll a=C; ll b=(ll)1<<K; ll c=B-A; ll x,y; ll g=extgcd(a,b,x,y); if(c%g!=0){ printf("FOREVERn"); } else { x*=c/g; b/=g; if(b<0)b=-b; ll ans=x%b; if(ans<0)ans+=b; printf("%lldn",ans); } }}