又一次遇到了碰撞类的题目，还是扩展gcd和同余模方程。上次博客的链接在这：。

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

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

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

　　具体代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 typedef long long ll; 7  8 ll n,m,k; 9 ll maxn;10 11 void ex_gcd(ll a,ll b,ll &x,ll &y,ll &g)12 {13     if(!b) {x=1;y=0;g=a;return;}14     ex_gcd(b,a%b,y,x,g);15     y -= a/b*x;16 }17 18 ll work(ll dx,ll dy)19 {20     ll g,x,y;21     ex_gcd(2*n,2*m,x,y,g);22     ll c = dy - dx;23     if(c % g) return maxn+1;24 25     x *= (c/g);26     ll mod = 2*m / g;27     x = (x%mod + mod) % mod;28 29     ll temp = 2*n*x + dx;30     if(temp<0 || temp>maxn) return maxn+1;31     else return temp;32 }33 34 ll solve(ll x,ll y)35 {36     ll ans = maxn + 1;37     ans = min(ans,work(x,y));38     ans = min(ans,work(-x,y));39     ans = min(ans,work(x,-y));40     ans = min(ans,work(-x,-y));41     if(ans == maxn+1) return -1;42     else return ans;43 }44 45 int main()46 {47     cin >> n >> m >> k;48     ll g = __gcd(n,m);49     maxn = n / g * m;50     while(k--)51     {52         ll x,y;53         scanf("%I64d%I64d",&x,&y);54         printf("%I64d\n",solve(x,y));55     }56 }