AcWing 1299. 五指山
原题链接
简单
作者:
LQstoic
,
2022-02-25 10:45:00
,
所有人可见
,
阅读 142
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e9+10;
int T;
int exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1;
y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int temp=y;
y=x-(a/b)*y;
x=temp;
return d;
}
int main()
{
cin>>T;
while(T--)
{
LL n,d,beg,end,x,y;
//本题题意为(beg+x*d) mod n = end
//转化为 beg+x*d-y*n=end
//即x*d-y*n =end-beg
cin>>n>>d>>beg>>end;
LL gcd=exgcd(n,d,x,y);
//cout<<gcd<<endl;
if((end-beg)%gcd)
{
puts("Impossible");
}
else
{
y*=(end-beg)/gcd;
n/=gcd;//保证得到的结果是最小正数
printf("%lld\n",(y%n+n)%n);
}
}
return 0;
}