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