Given two points A and B on the X-Y plane, output the number of the lattice points on the segment AB. Note that A and B are also lattice point. Those who are confused with the definition of lattice point, lattice points are those points which have both x and y co-ordinate as integer.
For example, for A (3, 3) and B (-1, -1) the output is 5. The points are: (-1, -1), (0, 0), (1, 1), (2, 2) and (3, 3).
Input Input starts with an integer T (≤ 125), denoting the number of test cases.
Each case contains four integers, Ax, Ay, Bx and By. Each of them will be fit into a 32 bit signed integer.
Output For each test case, print the case number and the number of lattice points between AB.
Sample Input 2 3 3 -1 -1 0 0 5 2 Sample Output Case 1: 5 Case 2: 2
#include <cstdio> #define ll long long ll abs(ll a,ll b){ if (a-b == 0) return 0; if (a-b < 0) return b-a; return a-b; } ll gcd(ll a,ll b){ return !b?a:gcd(b,a%b); } int main(){ int t; scanf("%d",&t); int kase = 1; while (t--){ int x1,y1,x2,y2; scanf("%ld%ld%ld%ld",&x1,&y1,&x2,&y2); printf("Case %d: ",kase++); ll up = abs(y2,y1); ll low = abs(x2,x1); printf("%lld\n",gcd(up,low)+1); } return 0; }原来写的。。。mdzz 一个gcd全部情况搞定
#include <cstdio> #define ll long long ll abs(ll a,ll b){ if (a-b == 0) return 0; if (a-b < 0) return b-a; return a-b; } ll gcd(ll a,ll b){ return !b?a:gcd(b,a%b); } int main(){ int t; scanf("%d",&t); int kase = 1; while (t--){ int x1,y1,x2,y2; scanf("%ld%ld%ld%ld",&x1,&y1,&x2,&y2); printf("Case %d: ",kase++); ll up = abs(y2,y1); ll low = abs(x2,x1); if (up == 0||low == 0) printf("%lld\n",up+low+1); else { ll ans = 0; if (up%low==0) ans = low+1; else { if (gcd(up,low) != 1) ans = 1 + gcd(up,low); else ans = 2; } printf("%lld\n",ans); } } return 0; }