poj1061,斐蜀定理

费蜀定理:
对于任意正整数x,y,一定存在整数a,b,使得:    ax+by=gcd(x,y);

定理1 gcd(a,b)是ax+by的线性组合的最小正整数
定理2 如果ax+by=c,x,y∈z;则c%gcd==0;
定理3 如果ab是互质的正整数,c是整数,且方程 ax+by=c有一组整数解x0y0,则此方程的一切整数解可以表示为x=x0+bt;y=y0-at;t∈z;(所以解都是第一组解的倍数)
#include <iostream>
#include <algorithm>

using namespace std;

int x,y,xn,yn,l;

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

int main(int argc, char** argv) {
	cin>>x>>y>>xn>>yn>>l;
	if(yn==xn){
		cout<<"Impossible\n";
		return 0;
	}
	if(yn>xn) swap(yn,xn),swap(y,x);
	long long s=(x>y)?y+l-x:y-x;
//cout<<s<<endl;
	int v=xn-yn;
	if(s%gcd(v,l)==0){
		while(s%v!=0) s+=l;
		cout<<s/v<<endl;
	}else cout<<"Impossible\n";
	return 0;
}


全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 12:30
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务