勾股数组（核心笔记）

· · 算法·理论

勾股数组

定义：满足a^2+b^2=c^2的三元正整数组(a,b,c)。

性质：a,b中必有一个3的倍数；a,b中必有一个4的倍数；a,b,c中必有一个5的倍数；ab是12的倍数；abc是60的倍数。

本原勾股数组

定义：满足gcd(a,b,c)==1的勾股数组。

结构：必为奇数^2+偶数^2=奇数^2。

本原勾股数组定理：令本原勾股数组(a,b,c)中a为奇数，b为偶数。每个本原勾股数组(a,b,c)一一对应：

记d=gcd(a,b,c)，则每个勾股数组(a,b,c)一一对应本原勾股数组(a/d,b/d,c/d)乘d，进而一一对应s,t和d，一一对应m,n和d。

勾股数组分解

给定正整数c，求所有满足c^2=a^2+b^2,a<b的正整数组(a,b)。

注：本原勾股数组分解不唯一。（e.g.65^2=16^2+63^2=33^2+56^2。）自然地，勾股数组分解也不唯一。

vector<pii> ppt[C];//ppt[c]：数值c的本原勾股数组分解{a,b}
vector<pii> pt[N];//pt[i]：第i个数c_i的勾股数组分解{a_i,b_i}

//求1~c的本原勾股数组分解
void get_ppt()
{
    for(int s=1;(s*s+1*1)/2<C;s+=2)
        for(int t=1;t<s && (s*s+t*t)/2<C;t+=2)
            if(gcd(s,t)==1)
                if(s*t<(s*s-t*t)/2) ppt[(s*s+t*t)/2].push_back({s*t,(s*s-t*t)/2});
                else ppt[(s*s+t*t)/2].push_back({(s*s-t*t)/2,s*t});
    return ;
}

get_ppt();

//求n个数c的勾股数组分解
for(int i=1;i<=n;i++)
{
    int c=read();
    for(int d=1;d*d<=c;d++)
        if(c%d==0)
        {
            for(auto it : ppt[d]) pt[i].push_back({it.first*(c/d),it.second*(c/d)});
            if(c/d!=d)
                for(auto it : ppt[c/d])
                    pt[i].push_back({it.first*d,it.second*d});
        }
}

例题

勾股数组分解方案数

补充。

给定一个正整数c，求所有满足c^2=a^2+b^2,a<b的正整数组(a,b)的个数f_1(c)。

下记p为满足p%4==1的质数，q为满足q%4==3的质数（即高斯质数）。

引理：给定一个正整数x，记质因数分解x=2^{u}\prod p_i^{v_i}\prod q_j^{w_j}，则所有满足x=a^2+b^2,a>0,b\geqslant0的整数组(a,b)的个数f_2(x)：

记质因数分解c=2^{u}\prod p_i^{v_i}\prod q_j^{w_j}，则c^2=2^{2u}\prod p_i^{2v_i}\prod q_j^{2w_j}，则f_1(c)=\frac{f_2(c^2)-1}{2}=\frac{(\prod(2v_i+1))-1}{2}。O(\sqrt C)。

应用：平面上的圆的整点问题

注：在勾股数组的基础上，还需补充c^2=0^2+c^2。