e005 - 王老先生有塊地

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算構成三角形的三個頂點之間，x 座標和 y 座標的差值的最大公因數之和。輸入為三角形三個頂點的座標 (x, y)，輸出為木樁的總數，即三個邊長的最大公因數之和。

解題思路

題目本質上是求三個線段長度的最大公因數之和。線段長度的計算方式是兩個頂點座標差值的絕對值。由於題目要求木樁只能打在座標點上，因此需要計算每個線段可以放置多少個木樁，這等同於線段長度的最大公因數。最後將三個線段的最大公因數加總即可得到答案。使用輾轉相除法 (Euclidean algorithm) 計算最大公因數。

複雜度分析

• 時間複雜度: O(log(max(abs(x1-x2), abs(y1-y2))))，其中 x1, x2, y1, y2 是座標值。這是因為 gcd 函數的時間複雜度是 log 級別的。由於有三個 gcd 計算，總時間複雜度仍然是 O(log(max(abs(x1-x2), abs(y1-y2))))。
• 空間複雜度: O(1)，因為只使用了常數級別的額外空間。

程式碼

#include <stdio.h>
#include <cmath>
int gcd(int a,int b){
    return (b==0)?a:gcd(b,a%b);
}
int main(){
	int a,b,c,d,e,f;
	while(scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f)){
		if(a==0&&b==0&&c==0&&d==0&&e==0&&f==0)break;
		printf("%d\n",gcd(abs(a-c),abs(b-d))+gcd(abs(a-e),abs(b-f))+gcd(abs(c-e),abs(d-f)));
	}
	return 0;
}