poj 1061カエルのデート(拡欧)

864 ワード

前からこの問題を書いたのを覚えていますが、死んでしまいました.ここ数日exgcdを見直し、noip 2012のd 2 t 1とこれをしました.
exgcdはx,yの値を参照で記録する
そしてpoj 1061をすると、ax=k(mod m)のa係数が正のように見えますか?a<0なら両側を-1に同乗しexgcdでxの特解を出す
特解x 0を求めるとすべてが容易になり,最小非負整数解(x 0%(m/gcd(a,m)+m/gcd(a,m)%(m/gcd(a,m))を容易に求めることができ,あるいはm/gcd(a,m)を周期としていくつかの条件を満たす解を求めることができる.
(btw,ax+by=c同理,1つの特解x 0*(c/gcd)を求めた後,同上の最小非負整数解を求めることもできるし,b/gcd(a,b)を周期として問題条件を満たす解を求めることもでき,x=x 0*(c/gcd)+(b/gcd)*k,kは任意の整数と通解することもできる.
前のコード
include
using namespace std;
#define ll long long
ll g,x,y,m,n,l,x0,p,q,c,a;
ll exgcd(ll a,ll b, ll&x,ll&y)
{
	int t,g;
	if (b==0){x=1;y=0;return a;}
	g=exgcd(b,a%b,x,y);
	t=x;x=y;y=t-(a/b)*y;
	return g;
}
void solve()
{
	if (m==n) {cout<0 
	g=exgcd(a,l,p,q);
	if (c%g!=0) {cout<>x>>y>>m>>n>>l;
	solve();
	return 0;
}