[置頂]POJカエルのデート1061【経典数論-拡張ユークリッド】
Language: Default
カエルのデート
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 98005
Accepted: 18548
Description
2匹のカエルがネットで知り合って、楽しく話していたので、一度会う必要があると思っていました.同じ緯度線に住んでいることを喜んで発見し、会うまで西に踊ることを約束した.しかし、彼らは出発する前に重要なことを忘れて、相手の特徴をはっきり聞いていないし、会う具体的な位置を約束していない.しかし、カエルたちは楽観的で、ずっとある方向に飛び降りれば、いつも相手に会えると思っています.しかし、この2匹のカエルが同じ時間に同じ点にジャンプしない限り、永遠に会うことはできません.この2匹の楽観的なカエルを助けるために、この2匹のカエルが会えるかどうか、いつ会えるかを判断するプログラムを書くように要求されました.
この2匹のカエルをそれぞれカエルAとカエルBと呼び,緯度線上の東経0度を原点とし,東から西へを正方向とし,単位長さ1メートルで首尾が接する数軸を得た.カエルAの出発点座標をx、カエルBの出発点座標をyとする.カエルAは一度にmメートル、カエルBは一度にnメートル、2匹のカエルが一度にジャンプするのにかかる時間は同じです.緯度線の総長はLメートルである.今、何回も踊ってから会うように頼んでください.
Input
入力には、x≠y<20000000,0Output
出会いに必要なジャンプ回数を出力し、永遠に会えない場合は「Impossible」を出力します.
Sample Input
浙江省
解題構想:経典数論題、拡張ユークリッドアルゴリズム.説明する
ACコード:
カエルのデート
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 98005
Accepted: 18548
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
出会いに必要なジャンプ回数を出力し、永遠に会えない場合は「Impossible」を出力します.
Sample Input
1 2 3 4 54浙江省
解題構想:経典数論題、拡張ユークリッドアルゴリズム.説明する
ACコード:
#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
if(b==0) return a;
return gcd(b,a%b);
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==0){
x=1;
y=0;
return a;
}
LL r=exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-a/b*y;
return r;
}
int main()
{
LL x,y,m,n,L;
while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L)!=EOF){
LL a=(n-m),b=L;
LL c=x-y;
LL r=gcd(a,b);
if(c%r){
printf("Impossible
");
continue;
}
a/=r;b/=r;c/=r;
LL s,k;
exgcd(a,b,s,k);
s*=c;
s%=b;
while(s<0) s+=b;
printf("%lld
",s);
}
return 0;
}