现在的位置: 首页 > 综合 > 正文

1477: 青蛙的约会 (扩展欧几里得算法)

2018年04月25日 ⁄ 综合 ⁄ 共 432字 ⁄ 字号 评论关闭
#include<iostream>
#include<cstdio>
#define ll long long
#define inf 0x7fffffff
using namespace std;
inline ll extend_gcd(ll a,ll b,ll &x,ll &y){
	if(b==0){x=1;y=0;return a;}
	else{
		int t=extend_gcd(b,a%b,y,x);
		y-=x*(a/b);
		return t;
	}
}
ll x,y,m,n,l,a,b,c,t;
int main(){
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    a=n-m;b=l;c=x-y;
    t=extend_gcd(a,b,x,y);
    if(c%t!=0){printf("Impossible\n");return 0;}
    a/=t;b/=t;c/=t;
    x=((c*x)%b+b)%b;
    if(!x)x+=b;
    printf("%lld\n",x);
    return 0;
}

抱歉!评论已关闭.