PKU 1061-取石子游戏

問題概要

x+mk=y+nk (mod L)を満す最小のKを求めよ．存在しない場合"Impossible"って出力せよ．

解法

式変形して1次合同方程式を解く
蟻本p260参照

実装(C++)

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long lli;
lli x,y,m,n,L;

long long extgcd(long long a,long long b,long long &x,long long &y){
	long long d=a;
	if(b!=0){
		d=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}else{
		x=1;y=0;
	}
	return d;
}

long long mod_inverse(long long a,long long M){
	long long x,y;
	extgcd(a,M,x,y);
	return (M+x%M)%M;
}
lli solve(lli a,lli b,lli M){
	lli t=__gcd(a,M);
	if(b%t!=0)return -1;
	a/=t;b/=t;M/=t;
	return mod_inverse(a,M)*b%M;
}
int main() {
	cin>>x>>y>>m>>n>>L;
	m-=n;
	x=y-x;
	x=(x+L)%L;
	m=(m+L)%L;
	if(m==0){
		cout<<"Impossible"<<endl;
		return 0;
	}
	lli ans=solve(m,x,L);
	if(ans==-1){
		cout<<"Impossible"<<endl;
	}else{
		cout<<ans<<endl;
	}
	return 0;
}