Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C. Ray Tracing 扩展欧几里得

C. Ray Tracing

链接：

http://codeforces.com/contest/724/problem/C

题解：

把矩形对称展开，最后小球在横纵坐标均为

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 ll r, INF, a, b, n, m, k;
 7 
 8 ll extend_gcd(ll a, ll b, ll &x, ll &y){
 9     if (b == 0) {
10         x = 1; y = 0;
11         return a;
12     }
13     else {
14         ll r = extend_gcd(b, a%b, y, x);
15         y -= x*(a / b);
16         return r;
17     }
18 }
19 
20 ll solve(ll x, ll y){
21     ll l = x + y;
22     if (l%r) return INF;
23     ll mod = -2 * m / r, k = a * l / r;
24     if (mod < 0) mod = -mod;
25     k = (k%mod + mod) % mod;
26     long long ret = 2 * n*k - x;
27     if (ret > 0 && ret < INF) return ret;
28     else return INF;
29 }
30 
31 int main()
32 {
33     cin >> n >> m >> k;
34     r = extend_gcd(n, m, a, b);
35     INF = n*m / r + 1;
36     r = extend_gcd(2 * n, -2 * m, a, b);
37     while (k--) {
38         ll x, y;
39         cin >> x >> y;
40         ll ans = INF;
41         ans = min(ans, solve(x, y));
42         ans = min(ans, solve(x, -y));
43         ans = min(ans, solve(-x, y));
44         ans = min(ans, solve(-x, -y));
45         if (ans != INF) cout << ans << endl;
46         else cout << -1 << endl;
47     }
48     return 0;
49 }