青蛙的約會
Description 兩只青蛙在網上相識了，它們聊得很開心，于是覺得很有必要見一面。它們很高興地發現它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。可是它們出發之前忘記了一件很重要的事情，既沒有問清楚對方的特征，也沒有約定見面的具體位置。不過青蛙們都是很樂觀的，它們覺得只要一直朝著某個方向跳下去，總能碰到對方的。但是除非這兩只青蛙在同一時間跳到同一點上，不然是永遠都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個程序來判斷這兩只青蛙是否能夠碰面，會在什么時候碰面。 Input 輸入只包括一行5個整數x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。 Output 輸出碰面所需要的跳躍次數，如果永遠不可能碰面則輸出一行"Impossible" Sample Input 1 2 3 4 5 Sample Output 4 Source |
解題思路：經典數論題，擴展歐幾里得算法。
AC代碼：
[cpp] view plaincopyprint?
#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\n");
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\n",s);
}
return 0;
}
版權聲明：本文為博主原創文章，轉載請注明出處。原文鏈接：http://blog.csdn.net/ydd97/article/details/47764735
本站文章版權歸原作者及原出處所有 。內容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責，本站只提供參考并不構成任何投資及應用建議。本站是一個個人學習交流的平臺，網站上部分文章為轉載，并不用于任何商業目的，我們已經盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯系我們，我們將根據著作權人的要求，立即更正或者刪除有關內容。本站擁有對此聲明的最終解釋權。
