LightOJ::1077 -----奇妙的最大公約數 - acm1314－IT工程師數位筆記本

文章出處

題目：http://www.lightoj.com/volume_showproblem.php?problem=1077

題意：在平面上，給出兩個點的坐標例如：（x， y）其中x， y 都是整數。求：以這兩個點為端點的線段上一共有幾個整數點（即：橫縱坐標皆為整數）。

解法：求出|x1 - x2| 和 |y1-y2| 的最大公約數再加上1 即可！

是不是很奇妙，不可思議的奇妙，為何如此的巧合呢？

然而就是如此的巧合！！！。

提示：把線段看做向量，把一個端點移到原點。式子中最后加那個 1 就是原點。

然后，，，，就比較難證啦，自己畫圖觀察吧。呵呵呵！

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

long long gcd(long long a, long long b)
{
    return b==0 ? a : gcd(b, a%b);
}

int main()
{
    int kase = 0;
    int T;
    cin>>T;
    while(T--)
    {
        long long x1, x2, y1, y2, a, b, ans = 0;
        cin>>x1>>y1>>x2>>y2;
        a=abs(x2-x1);
        b=abs(y2-y1);
        if(a==0) ans = b+1;
        else if(b==0) ans = a+1;
        else ans=gcd(a, b)+1;
        cout<<"Case "<<++kase<<": "<<ans<<endl;
    }
    return 0;
}