LightOJ

给你两个格点，求以它们为端点的线段上有多少个格点

答案为gcd(abs(x1-x2), abs(y1-y2)) + 1

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #define INF 0x3f3f3f3f
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 int T;
10 LL x1, y1, x2, y2;
11 
12 LL gcd(LL a, LL b) {
13     return b == 0 ? a : gcd(b, a % b);
14 }
15 
16 int main() {
17     scanf("%d", &T);
18     for (int t = 1; t <= T; t++) {
19         scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
20         printf("Case %d: %lld
", t, 1 + gcd(abs(x1 - x2), abs(y1 - y2)));
21     }
22     return 0;
23 }