题目：青蛙的约会

读完题，显然可以的到下同余方程:x+mk≡y+nk (mod L) 移项变成

(m-n)k+aL=y-x 只有k,L是未知的，而这题要求非负整数k的最小值，显然拓展欧几里得算法。

然后这题就做完了。

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#define int long long

using namespace std;

int ex,ey,n,m,l,x,y;

int exgcd(int a,int b,int &x,int &y)

{

	if(!b)

	{

		x=1,y=0;

		return a;

	}

	int d=exgcd(b,a%b,y,x);

	y-=a/b*x;

	return d;

}

signed main()

{

	scanf("%lld %lld %lld %lld %lld",&ex,&ey,&m,&n,&l);

	int d=exgcd(m-n,l,x,y);

	if((ey-ex)%d!=0)

	    puts("Impossible");

	else

	{

		x*=(ey-ex)/d;

		int t=abs(l/d);

		printf("%lld\n",(x%t+t)%t);

	}

	return 0;

}

巴特西

2022春每日一题：Day 25

题目：青蛙的约会

最新文章

热门文章