カエルのデート——ユークリッド—数論
2匹のカエルがネットで知り合って、楽しく話していたので、一度会う必要があると思っていました.同じ緯度線に住んでいることを喜んで発見し、会うまで西に踊ることを約束した.しかし、彼らは出発する前に重要なことを忘れて、相手の特徴をはっきり聞いていないし、会う具体的な位置を約束していない.しかし、カエルたちは楽観的で、ずっとある方向に飛び降りれば、いつも相手に会えると思っています.しかし、この2匹のカエルが同じ時間に同じ点にジャンプしない限り、永遠に会うことはできません.この2匹の楽観的なカエルを助けるために、この2匹のカエルが会えるかどうか、いつ会えるかを判断するプログラムを書くように要求されました.
この2匹のカエルをそれぞれカエルAとカエルBと呼び,緯度線上の東経0度を原点とし,東から西へを正方向とし,単位長さ1メートルで首尾が接する数軸を得た.カエルAの出発点座標をx、カエルBの出発点座標をyとする.カエルAは一度にmメートル、カエルBは一度にnメートル、2匹のカエルが一度にジャンプするのにかかる時間は同じです.緯度線の総長はLメートルである.今、何回も踊ってから会うように頼んでください.
Input
入力には、x≠y<20000000,0
Output
出会いに必要なジャンプ回数を出力し、永遠に会えない場合は「Impossible」を出力します.
Sample Input
Sample Output
Source
PKU
問題の意味から、これはユークリッドの問題であることがわかります.
拡張ユークリッドの定理:2つの不完全が0の整数aに対して、bは必ず1組の解xが存在し、yはax+by=gcd(a,b)になる.
#include
#include
long long x,y,q;
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
long long gcd_x(long long a,long long b)
{
long long t,d;
if(b==0)
{
x=1;
y=0;
return a;
}
d=gcd_x(b,a%b);
t=x;
x=y;
y=t-(a/b)*(y);
return d;
}
int main()
{
long long a,b,c,l,st1,st2,m,n,ans,k;
while(scanf("%lld %lld %lld %lld %lld",&st1,&st2,&m,&n,&l)==5)
{
a=n-m;
b=l;
c=st1-st2;
if(c%gcd(a,b)!=0) printf("Impossible");
else
{
ans=gcd_x(a,b);
x=x*(c/ans);
k=x/(b/ans);
x=x-k*(b/ans);
if(x<0) x=x+b/ans;
printf("%lld",x);
}
}
}
このコードの意識:
int gcd_x(int a,int b)
{
int t,d;
if(b==0)
{
x=1;
y=0;
return a;
}
d=gcd_x(b,a%b);
t=x;
x=y;
y=t-(a/b)*(y);
return d;
}
gcd(a,b)=gcd(b,a%b); a%b=a-a/b*b;
gcd(a,b)=ax+by=gcd(b,a%b)=bx1+(a%b)y1=y1*a+(x1-y1*a/b)*b
a b前対応係数が等しいことからx=y 1,y=x 1-y 1*(a/b)
上式x yは、本層の再帰的なx y(gcd(a,b)におけるx yと仮定する)x 1であり、y 1は前回の再帰的に返される
x y(gcd(b,a%b)におけるx y)
故有
t=x;
x=y;
y=t-(a/b)*(y); これらの文のコードはx yの値を求めます
gcd(a,b)=gcd(b,a%b)=gcd.........=gcd(a,0)=ax+by=a
この时ax+by=a x=1は疑いの余地がありませんが、yは何でもいいはずです.どうして0にしなければなりませんか.
k=x/(b/ans);
x=x-k*(b/ans);
if(x<0) x=x+b/ans;
上の3つの文は最も短い歩数を求めます
通解は
X=x0+b/ans*t
Y=y0-a/ans*t
上の3つの文は求めた最も短いステップ数である0より大きい最小の解である.
この2匹のカエルをそれぞれカエルAとカエルBと呼び,緯度線上の東経0度を原点とし,東から西へを正方向とし,単位長さ1メートルで首尾が接する数軸を得た.カエルAの出発点座標をx、カエルBの出発点座標をyとする.カエルAは一度にmメートル、カエルBは一度にnメートル、2匹のカエルが一度にジャンプするのにかかる時間は同じです.緯度線の総長はLメートルである.今、何回も踊ってから会うように頼んでください.
Input
入力には、x≠y<20000000,0
Output
出会いに必要なジャンプ回数を出力し、永遠に会えない場合は「Impossible」を出力します.
Sample Input
1 2 3 4 5
Sample Output
4
Source
PKU
問題の意味から、これはユークリッドの問題であることがわかります.
拡張ユークリッドの定理:2つの不完全が0の整数aに対して、bは必ず1組の解xが存在し、yはax+by=gcd(a,b)になる.
#include
#include
long long x,y,q;
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
long long gcd_x(long long a,long long b)
{
long long t,d;
if(b==0)
{
x=1;
y=0;
return a;
}
d=gcd_x(b,a%b);
t=x;
x=y;
y=t-(a/b)*(y);
return d;
}
int main()
{
long long a,b,c,l,st1,st2,m,n,ans,k;
while(scanf("%lld %lld %lld %lld %lld",&st1,&st2,&m,&n,&l)==5)
{
a=n-m;
b=l;
c=st1-st2;
if(c%gcd(a,b)!=0) printf("Impossible");
else
{
ans=gcd_x(a,b);
x=x*(c/ans);
k=x/(b/ans);
x=x-k*(b/ans);
if(x<0) x=x+b/ans;
printf("%lld",x);
}
}
}
このコードの意識:
int gcd_x(int a,int b)
{
int t,d;
if(b==0)
{
x=1;
y=0;
return a;
}
d=gcd_x(b,a%b);
t=x;
x=y;
y=t-(a/b)*(y);
return d;
}
gcd(a,b)=gcd(b,a%b); a%b=a-a/b*b;
gcd(a,b)=ax+by=gcd(b,a%b)=bx1+(a%b)y1=y1*a+(x1-y1*a/b)*b
a b前対応係数が等しいことからx=y 1,y=x 1-y 1*(a/b)
上式x yは、本層の再帰的なx y(gcd(a,b)におけるx yと仮定する)x 1であり、y 1は前回の再帰的に返される
x y(gcd(b,a%b)におけるx y)
故有
t=x;
x=y;
y=t-(a/b)*(y); これらの文のコードはx yの値を求めます
gcd(a,b)=gcd(b,a%b)=gcd.........=gcd(a,0)=ax+by=a
この时ax+by=a x=1は疑いの余地がありませんが、yは何でもいいはずです.どうして0にしなければなりませんか.
k=x/(b/ans);
x=x-k*(b/ans);
if(x<0) x=x+b/ans;
上の3つの文は最も短い歩数を求めます
通解は
X=x0+b/ans*t
Y=y0-a/ans*t
上の3つの文は求めた最も短いステップ数である0より大きい最小の解である.