POJカエルのデート(拡張ユークリッド)
10111 ワード
カエルのデート
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)
Total Submission(s) : 2 Accepted Submission(s) : 2
Problem Description
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
1 2 3 4 5
Sample Output
4
Source
PKU
詳細:
http://www.cnblogs.com/comeon4mydream/archive/2011/07/18/2109060.html
http://www.cnblogs.com/jian1573/archive/2012/07/22/2603943.html
まず,ユークリッドアルゴリズム(gcd)について議論する.
gcd(a,b)は2つの数の最大公約数を求める
再帰アルゴリズム:
int gcd( int a, int b ) { return b==0?a:gcd( b, a%b ); //gcd(a,b)=gcd(a%b,b)は,この再帰が1回終了するとa bが減少し続けることが保証されないため,bとa%bを順番に交換する.
非再帰アルゴリズム:
int gcd( int a, int b ) { if( b==0 )return 0; while(b) { int t=a%b; a=b; b=t; } return a;
}
ここでアルゴリズムの正しさ、すなわちgcd(a,b)=gcd(b,a%b)を証明することについて議論する.gcd(a,b)=gcd(a,b)=gcd(a−b,b)を証明すればよい.これによりgcd(a,b)==gcd(a−k*b,b)に徐々に拡張できるため、gcd(a−k*b)==gcd(a%b)==gcd(a%b,b)=gcd(a%b,b)に拡張できる.a,bの公約数は必然的にa−b,bの公約数であるため、gcd(a,b)<=gcd(a−b,b);また、a−bの公約数は約数も必然的にa bの公約数,gcd(a,b)>=gcdである.(a-b,b).従ってgcd(a,b)==gcd(a-b,b).
ユークリッドを拡張するには
拡張ユークリッドアルゴリズムは、a*x+b*y=gcd(a,b)のような方程式を解くために用いられる.同様にgcd(a,b)=gcd(b,a%b)を用いてa*x+b*y=gcd(a,b)をb*x'+(a%b)*y'=gcd(b,a%b)に変換する.
再帰的な考え方に基づいて、現在x'y'を求めていると仮定すると、残りの鍵はどのようにx'y'でx y y yを求めるかである.gcd(b,a%b)=b*x'+(a%b)*y'を観察し、右側をa*x+b*yの形式に書き直すだけでよいので、b*x'+(a%b)*y'を変形する必要がある.a%b==a-a/a/b*b*bであるため、b*x'+(a%b)y'=b*x'+(a-a/b*b*b)y'==a*y'+(x*y'+(x*y'==a*y'+(x*y'+(x*y'+'-a/b*y').
これにより、x=y′y=x′−a/b*y′が得られる.
拡張gcdの再帰アルゴリズムは
LL exgcd( LL a, LL b, LL &x, LL &y ) { LL d, t; if( b==0 ) { x=1, y=0; return a; } d=exgcd( b, a%b, x, y ); t=x, x=y, y=t-a/b*y; return d; //gcd(a,b);}を返す
方程式の解を得ました
x==x0+b*t; // 特解+通解
y==y0+a*t;
それから一般的な形式a*x+b*y==cを見ます.
c%gcd(a,b)=0の場合にのみ方程式が解ける.
a*x+b*y=cの解は,まずa*x+b*y=gcd(a,b)を求め,その後x yをc/gcd(a,b)倍に拡大すればよい.
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)
Total Submission(s) : 2 Accepted Submission(s) : 2
Problem Description
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
1 2 3 4 5
Sample Output
4
Source
PKU
詳細:
http://www.cnblogs.com/comeon4mydream/archive/2011/07/18/2109060.html
http://www.cnblogs.com/jian1573/archive/2012/07/22/2603943.html
まず,ユークリッドアルゴリズム(gcd)について議論する.
gcd(a,b)は2つの数の最大公約数を求める
再帰アルゴリズム:
int gcd( int a, int b ) { return b==0?a:gcd( b, a%b ); //gcd(a,b)=gcd(a%b,b)は,この再帰が1回終了するとa bが減少し続けることが保証されないため,bとa%bを順番に交換する.
非再帰アルゴリズム:
int gcd( int a, int b ) { if( b==0 )return 0; while(b) { int t=a%b; a=b; b=t; } return a;
}
ここでアルゴリズムの正しさ、すなわちgcd(a,b)=gcd(b,a%b)を証明することについて議論する.gcd(a,b)=gcd(a,b)=gcd(a−b,b)を証明すればよい.これによりgcd(a,b)==gcd(a−k*b,b)に徐々に拡張できるため、gcd(a−k*b)==gcd(a%b)==gcd(a%b,b)=gcd(a%b,b)に拡張できる.a,bの公約数は必然的にa−b,bの公約数であるため、gcd(a,b)<=gcd(a−b,b);また、a−bの公約数は約数も必然的にa bの公約数,gcd(a,b)>=gcdである.(a-b,b).従ってgcd(a,b)==gcd(a-b,b).
ユークリッドを拡張するには
拡張ユークリッドアルゴリズムは、a*x+b*y=gcd(a,b)のような方程式を解くために用いられる.同様にgcd(a,b)=gcd(b,a%b)を用いてa*x+b*y=gcd(a,b)をb*x'+(a%b)*y'=gcd(b,a%b)に変換する.
再帰的な考え方に基づいて、現在x'y'を求めていると仮定すると、残りの鍵はどのようにx'y'でx y y yを求めるかである.gcd(b,a%b)=b*x'+(a%b)*y'を観察し、右側をa*x+b*yの形式に書き直すだけでよいので、b*x'+(a%b)*y'を変形する必要がある.a%b==a-a/a/b*b*bであるため、b*x'+(a%b)y'=b*x'+(a-a/b*b*b)y'==a*y'+(x*y'+(x*y'==a*y'+(x*y'+(x*y'+'-a/b*y').
これにより、x=y′y=x′−a/b*y′が得られる.
拡張gcdの再帰アルゴリズムは
LL exgcd( LL a, LL b, LL &x, LL &y ) { LL d, t; if( b==0 ) { x=1, y=0; return a; } d=exgcd( b, a%b, x, y ); t=x, x=y, y=t-a/b*y; return d; //gcd(a,b);}を返す
方程式の解を得ました
x==x0+b*t; // 特解+通解
y==y0+a*t;
それから一般的な形式a*x+b*y==cを見ます.
c%gcd(a,b)=0の場合にのみ方程式が解ける.
a*x+b*y=cの解は,まずa*x+b*y=gcd(a,b)を求め,その後x yをc/gcd(a,b)倍に拡大すればよい.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long Gcd(long long a,long long b){
return b==0?a: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 tmp=x;
x=y;
y=tmp-a/b*y;
}
int main(){
//freopen("input.txt","r",stdin);
long long x,y,m,n,L;
long long a,c,k1,k2,r;
while(~scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L)){
a=n-m; c=x-y;
r=Gcd(a,L);
if(c%r){
puts("Impossible");
continue;
}
a/=r; L/=r; c/=r;
exGcd(a,L,k1,k2);
long long ans=c*k1-c*k1/L*L;
if(ans<0)
ans+=L;
printf("%I64d
",ans);
}
return 0;
}#include <stdio.h>
typedef long long LL;
LL exgcd( LL a, LL b, LL &x, LL &y )
{
LL d, t;
if( b==0 )
{
x=1, y=0;
return a;
}
d=exgcd( b, a%b, x, y );
t=x, x=y, y=t-a/b*y;
return d;
}
// (a+c*m)%2^k=b ==> c*m-n*2^k=b-a;
int main( )
{
LL A,B,C,k, a, b, c, x, y, n;
while(scanf("%lld %lld %Illd %lld",&A,&B,&C,&k))
{
if(!A && !B && !C && !k)
break;
a=C, b=B-A, n=(LL)1<<k; //2^k
LL d=exgcd(a,n,x,y); // a,n d=gcd(a,n) d=ax+by x、y
if(b%d!=0) // ax=b(mod n)
puts("FOREVER");
else
{
x=(x*(b/d))%n; // ax=b(mod n)
x=(x%(n/d)+n/d)%(n/d); // ax=b(mod n)
printf("%lld
",x);
}
}
return 0;
}