danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29164

[BZOJ 1477]青蛙的约会

2016年8月28日 19:59 | Comments(0) | Category:题解 | Tags:

设用时为[tex]t[/tex],则本题可视为解方程[tex](mt+x)-(nt+y)=kL[/tex]。

整理变形得[tex](n-m)t+Lk=x-y[/tex]。

明显需要扩欧求解。注意此题有很多细节,可参见下代码:

/**************************************************************
    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;
}