CodeForces 724C Ray Tracing（碰撞类，扩展gcd）

　　又一次遇到了碰撞类的题目，还是扩展gcd和同余模方程。上次博客的链接在这：http://www.cnblogs.com/zzyDS/p/5874440.html。

　　现在干脆解同余模直接按照套路来吧，如果有解，那么x先乘以（c/g），然后mod数是（b/g），就按照这个套路来好了- -。

　　这题的思路大概是这样的，首先碰到墙壁的角肯定会在lcm(n,m)时刻发生，这之后是原路返回的，也就是说如果在这个时间之前都没有碰到的点一定是永远碰不到的。

　　对每一个点(x0,y0)来说，解 2nx+(-)x0 = 2ny+(-)y0。其中x和y是变量，那么移项以后显然是同余模方程。我们关于x0和y前的符号作一下讨论，解四个方程，取最小即可。

　　具体代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 using namespace std;

 typedef long long ll;

 ll n,m,k;

 ll maxn;

 void ex_gcd(ll a,ll b,ll &x,ll &y,ll &g)

 {

     if(!b) {x=;y=;g=a;return;}

     ex_gcd(b,a%b,y,x,g);

     y -= a/b*x;

 }

 ll work(ll dx,ll dy)

 {

     ll g,x,y;

     ex_gcd(*n,*m,x,y,g);

     ll c = dy - dx;

     if(c % g) return maxn+;

     x *= (c/g);

     ll mod = *m / g;

     x = (x%mod + mod) % mod;

     ll temp = *n*x + dx;

     if(temp< || temp>maxn) return maxn+;

     else return temp;

 }

 ll solve(ll x,ll y)

 {

     ll ans = maxn + ;

     ans = min(ans,work(x,y));

     ans = min(ans,work(-x,y));

     ans = min(ans,work(x,-y));

     ans = min(ans,work(-x,-y));

     if(ans == maxn+) return -;

     else return ans;

 }

 int main()

 {

     cin >> n >> m >> k;

     ll g = __gcd(n,m);

     maxn = n / g * m;

     while(k--)

     {

         ll x,y;

         scanf("%I64d%I64d",&x,&y);

         printf("%I64d\n",solve(x,y));

     }

 }