首页 > 代码库 > POJ 2115

POJ 2115

2024-07-20 05:45:04   215人阅读

和POJ 1061一样

要求最小解，就尽可能的把ax的值附到by上去，所以可以有ax=b*k+a*v（因为附到by上后必须仍上a*x的形式）。两边同除a就可得到结果。

但是，我们知道，（a,b）=1。所以k|a，也就是说，ans=(x%b+b)%b。后来加上b是为了防止负数。

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;__int64 gcd(__int64 a,__int64 b){	if(b==0) return a;	return gcd(b,a%b);}void exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y){	if(b==0){		x=1; y=0;		return ;	}	exgcd(b,a%b,x,y);	__int64 tmp=x;	x=y;	y=tmp-(a/b)*y;}int main(){	__int64 A,B,C,k,a,b,c;	__int64 x,y;	while(scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&k)&&A+B+C+k>0){		k=1LL<<(k);		if(A==B){			printf("0\n"); continue;		}		__int64 tmp;		a=C; b=k; c=B-A;		tmp=gcd(a,b);		if(c%tmp!=0){			printf("FOREVER\n");			continue;		}		a/=tmp; b/=tmp; c/=tmp;		exgcd(a,b,x,y);		x*=c;		tmp=(x%b+b)%b;		printf("%I64d\n",tmp);	}	return 0;}

　　

POJ 2115


联系
我们