首页 > 代码库 > 扩张欧几里得
扩张欧几里得
#include <iostream>#include <cstdio>#include <queue>#include <algorithm>#define ll long longusing namespace std;ll ext_gcd(ll a, ll b, ll &p, ll &q){ ll t, r; if(!b){ p = 1; q = 0; return a; } r = ext_gcd(b,a%b,p,q); t = p; p = q; q = t -(a/b)*q; return r;}int main(){ ll x, y, n, m, l; ll t, a, b, d, r, c; ll p, q; scanf("%lld %lld %lld %lld %lld",&x,&y,&n,&m,&l); a = n-m; c = y-x; b = l; d = ext_gcd(a,b,p,q); if(c%d != 0) printf("Impossible"); else { p = p*(c/d); p = (p%b+b)%b; printf("%lld\n",p); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。