Ray Tracing
题目链接：http://codeforces.com/problemset/problem/724/C
拓展欧几里得
//为什么这次C题这么难啊=。=
可以观察到，光线在矩形中运动的时间为LCM（n，m），所以可以把整个矩阵扩展成LCM（n，m）*LCM（n，m）的矩阵[光线从（0,0）点一直射到（LCM（n，m），LCM（n，m））点]，然后将点关于矩形的四条边变换到直线y=x上，取最小的即可。
变换后得到的点的纵坐标为2*p*n±X，横坐标为2*q*m±Y，因为要求在直线y=x上，故2*p*n±X=2*q*m±Y，移项得2*p*n-2*q*m=±X±Y。
而拓展欧几里得可以解不定方程a*x+b*y=c，其中c=GCD（a，b），令a=2*n，b=-2*m，求得x和y。
将方程a*x+b*y=c变换成2*p*n-2*q*m=±X±Y，得到p或q，求出2*p*n±X或2*q*m±Y即可。
//注意求得的p或q要为自然数
代码如下：
#include<iostream>
#include<cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const LL INF=;
LL GCD(LL a,LL b){
return b==?a:GCD(b,a%b);
}
LL exGCD(LL a,LL b,LL &x,LL &y){
if(b==){
x=,y=;
return a;
}
LL t=exGCD(b,a%b,x,y);
LL r=x;x=y;y=r-a/b*y;
return t;
}
LL LCM(LL a,LL b){
LL gcd=GCD(a,b);
return (a/gcd)*b;
}
LL n,m,k,x,y,p,q,a,b,lim,mul;
LL mix(LL x,LL y){
LL t=x-y;
if(t%mul!=)return INF;
t/=mul;
p=a*t;
LL mod=abs((-*m)/mul);//mod is the t of p*x*t-q*y*t=gcd*t
p=(p%mod+mod)%mod;
LL tmp=INF;
LL tt=*n*p-x;
if(<tt&&tt<=lim)tmp=min(tmp,tt);
return tmp;
}
int main(void){
scanf("%I64d%I64d%I64d",&n,&m,&k);
lim=LCM(n,m);
for(LL i=;i<k;++i){
scanf("%I64d%I64d",&x,&y);
mul=exGCD(*n,-*m,a,b);
//mul=GCD(2*n,-2*m);
LL ans=INF;
ans=min(ans,mix(-x,y));
ans=min(ans,mix(x,y));
ans=min(ans,mix(-x,-y));
ans=min(ans,mix(x,-y));
if(ans<INF)printf("%I64d\n",ans);
else printf("-1\n");
}
}