NC50575. 五指山
描述
输入描述
有多组测试数据。
第一行是一个正整数T，表示测试数据的组数；
每组测试数据包括一行，四个非负整数，分别为如来手掌圆圈的长度n，筋斗所能飞的距离d，大圣的初始位置x和大圣想去的地方y。
注意孙悟空的筋斗云只沿着逆时针方向翻。
输出描述
对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。如果无论翻多少个筋斗云也不能到达，输出Impossible。
示例1
输入:
2 3 2 0 2 3 2 0 1
输出:
1 2
C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 484K, 提交时间: 2019-08-26 16:12:05
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1;
y=0;
return a;
}
ll d=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-y*(a/b);
return d;
}
int main(){
ll n,d,x,y;
int T;
scanf("%d",&T);
while(T--){
scanf("%lld%lld%lld%lld",&n,&d,&x,&y);
ll a=d,b=n,x1,y1,c=y-x;
ll d1=exgcd(a,b,x1,y1);
if(c%d1!=0)
puts("Impossible");
else{
x1=x1*c/d1;
b=b/d1;
b=abs(b);
x1=(x1%b+b)%b;
printf("%lld\n",x1);
}
}
return 0;
}
C++ 解法, 执行用时: 14ms, 内存消耗: 504K, 提交时间: 2021-07-12 11:17:04
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return d;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll n,d,x,y;
cin>>n>>d>>x>>y;
ll x1,y1;
ll div=exgcd(d,n,x1,y1);
ll tt=abs(n/div);
if((y-x)%div) puts("Impossible");
else cout<<(x1%tt*(y-x)/div%tt+tt)%tt<<endl;
}
return 0;
}