poj 1061 青蛙的约会

Description

Input

Output

Sample Input

1 2 3 4 5

Sample Output

4

分析：

样例：

x,y,m,n,l

1 2 3 4 5

设x为跳跃次数.

根据题目意思可构建方程：1+(3*x)%5=2+(4*x)%5=k

令上式等于k.

则：(3*x)%5=k-1 

       (4*x)%5=k-2 

即：3*x=5*k1+(k-1)  .........(1)

       4*x=5*k2+(k-2)  .........(2)    (k1,k2为任意正整数)

所以：由(1)-(2)得：-x=5(t1-t2)+1 ----->  -x=5*y+1  ----->  -x-5y=1  (令y=t1-t2)

根据扩展欧几里得，求解方程 -x-5*y=1  (a*x+b*y=c)

#include<stdio.h>
#include<iostream>
using namespace std;

typedef __int64 ll;
ll gcd(ll a,ll b,ll &x1,ll &y1)
{
  ll k;
  if(b==0) 
  {
	  x1=1;
	  y1=0;
	  return a;
  }
  else 
  {
	  k=gcd(b,a%b,y1,x1);
      y1-=x1*(a/b);
  }
  return k;
}

int main ()
{
  ll x,y,n,m,l;
  ll a,b,d,t;
  ll x1,y1;
  while(~scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&n,&m,&l))
  {
	  a=n-m;
      c=y-x; 
	  d=gcd(a,l,x1,y1);
	  if(c%d!=0)
	  {
	    printf("Impossible\n");
		continue;
	  }
	  t=l/d;
	  x1=(c/d*x1+t)%t;
	  while(x1<0) 
	  {
		  x1+=l;
	  }
	  printf("%I64d\n",x1);
  }
  return 0;
}

poj 1061 青蛙的约会,布布扣,bubuko.com

poj 1061 青蛙的约会

原文：http://blog.csdn.net/fyxz1314/article/details/38513625