[BZOJ 1477]青蛙的约会
设用时为，则本题可视为解方程
。
整理变形得。
明显需要扩欧求解。注意此题有很多细节，可参见下代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | /************************************************************** Problem: 1477 User: danihao123 Language: C++ Result: Accepted Time:0 ms Memory:1288 kb****************************************************************/ #include <iostream>using namespace std;typedef long long ll;ll gcd(ll a,ll b){ if(!b) return a; else return gcd(b,a%b);}void exgcd(ll a,ll b,ll &d,ll &x,ll &y){ if(!b){ d=a; x=1; y=0; }else{ exgcd(b,a%b,d,x,y); ll t=x; x=y; y=t-a/b*y; }}int main(){ ll a,b,c,t,M,k; ll x,y,m,n,L; cin>>x>>y>>m>>n>>L; a=n-m; b=L; c=x-y; k=gcd(a,b); if(c%k!=0){ cout<<"Impossible"<<endl; return 0; } a/=k; b/=k; c/=k; exgcd(a,b,k,t,M); t=(((c*t)%b)+b)%b; if(!t) t+=b; cout<<t<<endl; return 0;} |
