前置知识

高斯整数（推荐）

定义与性质

对于$a^2+b^2=c^2$，且$gcd(a,b,c)=1$，那么$a,b$定为一奇一偶，$c$为奇数，我们约定$a$为奇数，$b$为偶数

每个本原勾股数组$(a, b, c)$，都可以由一对互质的整数$s,t$得出

$s^2=c+b,\ t^2=c-b$

该三角形的周长$C=s(s+t)$

$a=st, b=\frac{s^2-t^2}{2}, c=\frac{s^2+t^2}{2}\ (s>t>0)$

下面证明$c+b,c-b$必是平方数

$$a^2=s^2t^2$$

设$gcd(b-c,b+c)=d$，则$d\mid ((b-c)+(b+c)), d\mid ((b+c)-(b-c))$，即$d\mid 2b, d\mid 2c$

因为$2\not \mid (b+c)$，因此$d\mid b, d\mid c$，又因为$gcd(b,c)=1$，因此$b-c, b+c$互质。

进而有$s^2,t^2$互质

因为$a^2$为平方数，因此$s,t$为平方数。

上述过程同时也证明了$s,t$互质

其他性质

$(a,b,c)$中$a,b$有且仅有一个是3的倍数，$c$不是3的倍数

$(a,b,c)$中有且只有一个为5的倍数

例题

51nod 1165 (opens new window)

题目：直角三角形，三条边的长度都是整数。给出周长$N$，求符合条件的三角形数量。

由于周长$C=s(s+t)$，且$N\le1e7$，那么我们可以遍历$s$，可知$s<sqrt(1e7)$，求出所有本原直角三角形

AC代码如下（关闭流同步后，耗时:375ms）复杂度: 近似$O(n)$

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 1e7 + 100;
int ans[maxn]={0}, t, n;

int main(){
    ll limit = sqrt(maxn)+1, cir;
    for(int s=3; s<=limit; s+=2){ // s为奇数
        for(int t=1; t<s; t+=2){ // t为奇数
            if(__gcd(s, t) != 1) continue;
            cir = s*(s+t);
            for(int k=1; k*cir<maxn; k++) ans[k*cir]++; // 计算贡献
        }
    }
    cin >> t;
    while(t--) {
        cin >> n;
        cout << ans[n] << '\n';
    }
}

参考资料

走进数论——神奇的勾股数组 (opens new window)

【数论】本原勾股数组(PPT)的性质 (opens new window)