ACM – Uva106 – 勾股定理

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

給一個任意數對(X,Y),用以下公式代替

$A = X^2 – Y^2$

$B = 2XY$

$C = X^2 + Y^2$

得出的A,B,C就是一組勾股數。

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

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

按照台湾同胞的题解。 — 勾股数公式也是很神奇的啊。。。

此外还学习了bitset,因为是按位存储,所以比一般的bool来的更加迅速,也更加节省时间。