UVa 106 Fermat vs. Pythagoras

解題策略:

勾股定理 A²+B²=C²，或者叫做畢氏定理，符合公式的數對(A,B,C)就叫一組勾股數 (畢氏三元數)。

題目給一個正整數N，要我們找出兩個答案，第一: 0~N之間總共有幾組互質勾股數? 第二: 0~N之間有幾個數完全不屬於任何一組勾股數? 我舉個例子N=10，那麼0~10之間可以找到兩組勾股數(3,4,5)與(6,8,10)，其中只有(3,4,5)一組互質，所以第一個答案是1。再來，3,4,5,6,8,10 都屬於某一組勾股數，完全沒用到的數字是1,2,7,9，共四個數，所以第二個答案是4。

解題關鍵在於如何快速找出一堆勾股數。我想就別折騰了，要解這題就要知道勾股數的通解，單純用暴力搜尋鐵定超時。

從維基百科的勾股數條目參考來的通解：

給一個任意數對(X,Y)，用以下公式代
A = X² - Y²
B = 2XY
C = X² + Y²
得出的A,B,C就是一組勾股數。

若 (X,Y) 恰好互質而且一奇一偶，那麼會得到一組(A,B,C)互質的勾股數。

知道通解後，雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。

找出不屬於勾股數的數字，直接開一個 size=1000000 的陣列來記錄所有出現過的數字 (用array或是bitset都成)。別忘了一點，我們上面只列出互質的勾股數，但是勾股數的任意整數倍也都是勾股數，如(3,4,5) (6,8,10) (9,12,15)，這些數字也都必須列入紀錄。

閒聊

我知道Fermat是費瑪，不過標題看很久才發現P先生是畢達哥拉斯orz，對於世界第一的先生(Runtime 0.008秒 by Java)，感到由衷的敬佩。

	/**
	* UVa 106 Fermat vs. Pythagoras
	* Author: chchwy
	* Last Modified: 2011.03.20
	* Tag: Math, Pythagorean triples
	*/
	#include<cstdio>
	#include<cstring>
	#include<cmath>
	short int p[1000001];
	int gcd(int m, int n)
	{
	int k;
	while (k = m % n)
	{
	m = n;
	n = k;
	}
	return n;
	}
	int main()
	{
	int max;
	while (scanf("%d", &max) == 1)
	{
	int numTuple = 0; //number of tuple(a,b,c)
	memset(p, 0, sizeof(p));
	// 用雙層迴圈跑遍(x,y)所有可能的值
	for (int x = 1; x < 1000; ++x)
	{
	for (int y = x + 1;; y += 2)
	{
	if (gcd(x, y) != 1) continue;
	int a, b, c; //tuple(a,b,c)
	a = y * y - x * x;
	b = 2 * x * y;
	c = y * y + x * x;
	if (c > max) break;
	numTuple++;
	int ma = a, mb = b, mc = c;
	while (mc <= max)
	{
	p[ma] = p[mb] = p[mc] = 1;
	ma += a;
	mb += b;
	mc += c;
	}
	}
	}
	int numNotInTuple = max;
	for (int i = 0; i <= max; ++i)
	numNotInTuple -= p[i];
	printf("%d %d\n", numTuple, numNotInTuple);
	}
	return 0;
	}

view raw 106.cpp hosted with ❤ by GitHub