在此记录一些本人百打百挂的板子：
1. 扩展欧几里得（以青蛙的约会为模板）
题意：给出n,m,x,y,l，求g*l+k*(n-m)=x-y中k的最小正整数解
做法：明显是扩欧板子虽然我不会写
注意n-m为负数时，将n-m与x-y同时取相反数即可
记住x=y1,y=x1-a/b*y1
当求出ax+by=gcd(a,b)的特解后，通解为y=y0-(a/gcd)*t,x=x0+(b/gcd)*t
上代码
#include <cstdio> inline long long int gcd(long long int a,long long int b){return b==0?a:gcd(b,a%b);} inline void exgcd(long long int a,long long int b,long long int &x,long long int &y){ if(b==0){ x=1,y=0; return; } long long int x1,y1; exgcd(b,a%b,x1,y1); x=y1,y=x1-a/b*y1; return; } int main(void){ long long int xx,yy,mm,nn,ll; scanf("%lld%lld%lld%lld%lld",&xx,&yy,&mm,&nn,&ll); long long int a=ll,b=mm-nn,c=yy-xx; if(b<0) b=-b,c=-c; long long int d=gcd(a,b); if(c%d){ printf("Impossible"); return 0; } else{ a/=d,b/=d,c/=d; long long int x,y; exgcd(a,b,x,y); printf("%lld\n",((y*c)%a+a)%a); } }
原文：https://www.cnblogs.com/Pride205/p/11811558.html
