当前位置：首页 > article >正文

P1516 青蛙的约会(exgcd)

article 2025/2/21 3:33:17

一些前置知识：

1.扩展欧几里得算法：

ax+by=gcd(a,b)

方程一个可行的解（x1,y1）求法：

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;
}

2.由ax+by=gcd(a,b) 的解推出 ax+by=n 的一个可行解（x0,y0）:

3.由ax+by=n 的解（x0,y0）推其通解：

4.在通解中找最小正整数解的小技巧：

设y=t*x+z(t、z为常数，x为变量) ,则y 的最小正整数解为：

y`=(z%t+t)%t;

正式进入题解：

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 

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()
{
	int x,y,m,n,l,x0,y0; 
	cin>>x>>y>>m>>n>>l;
	int a=m-n,b=y-x;
	if(a<0) a=-a,b=-b;//注意gcd仅仅对正整数有意义，故要将系数化为正数
	int d=exgcd(a,l,x0,y0);//扩欧
	if(b%d) cout<<"Impossible";//判断原方程是否有解
	else {
		int k=l/d;
	cout<<(x0*(b/d)%k+k)%k;//求最小正整数解
	}
	
}

24/8/29

查看全文

http://www.kler.cn/a/282159.html