T30550: 勾股数

http://cs101.openjudge.cn/practice/30550/

给你一个整数 n ，请找到所有的三元组 (a,b,c) 使得：1 ≤ a < b < c ≤ n 并且 a2 + b2 = c2

输入

一行，一个整数 n (1 ≤ n ≤ 10^6)

输出

共一行，按照字典序输出所有的勾股数三元组 a,b,c，三元组与三元组间以及三元组内部均用空格隔开。

样例输入

sample1 input:
5

sample1 output:
3 4 5

样例输出

sample2 input:
20

sample2 output:
3 4 5 5 12 13 6 8 10 8 15 17 9 12 15 12 16 20

提示

tags:math,number theory

来源

yxq, 2026 winter, https://codeforces.com/gym/664677/problem/D

【尹显齐 2500011456 物理学院】

这个题给的 $n$ 范围很大，使用传统的 $O(n^2)$ 的方法明显不行。下面提供两种方法。 法一： 见 https://file.murasame.site/shared/cp/cf/contest-1-solution.pdf 的第七页

法二：
我们可以通过寻找本源勾股数（$a,b,c$ 互质的三元组），再不断乘倍数得到所有勾股数。
欧几里得告诉我们，生成的方式为

$$a=m^2-n^2$$$$b=2mn$$$$c=m^2+n^2$$

容易证明，当 $m,n$ 奇偶性不同且互质时，生成的 $a,b,c$ 是互质的。
但是： 直接生成所有数对并排序会爆时间和内存。此时需要一点小巧思（见 https://codeforces.com/blog/entry/150214 评论区），采用位运算将三个数 $a,b,c$ 变成一个数，再进行排序，才能通过。（C++也许是不需要的？）
时间复杂度：$O(n{\log }^{2}n)$

代码：

import math
import sys
N = int(input())
triples = []
for m in range(2,int(math.sqrt(N))+1):
    for n in range(1,m):
        if math.gcd(m,n) != 1 or (m % 2) == (n % 2):
            continue
        a0 = m*m - n*n
        b0 = 2*m*n
        c0 = m*m + n*n
        if a0 > b0:
            a0,b0 = b0,a0 # 确保a0<b0
        k = 1
        while k*c0 <= N:
            a,b,c = k*a0,k*b0,k*c0
            triples.append((a<<40)|(b<<20)|c)# 使用位运算，2**20>10**6
            k += 1
triples.sort()
res = []
mask = (1 << 20) - 1
for i,tri in enumerate(triples):
    if i == 0 or tri != triples[i-1]:# 去重
        sys.stdout.write(f"{tri>>40} {(tri>>20)&mask} {tri&mask} ")