自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 21:24:39，当前版本为作者最后更新于2024-02-17 00:27:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

初见这个方程并无想法，但是通过打表观察发现，如果有一组解 $(a,b,c)$（这里假设 $a<b<c$），大概就会有一组解 $(b,c,x)$，这启发我们通过一组解来扩展出其他解。

若有解 $(a,b,c)$，则 $a^2 - k(b+c)a + (b^2+c^2-kbc-1)=0$。

这是二次方程组，通过韦达定理，得到 $a_1+a_2 = k(b+c)$，$x=k(b+c)-a$ 是这个方程的另一个解。

又由于 $b,c>a$，因此 $k(b+c)-a>0$，于是我们找到了新的解 $(b,c,k(b+c)-a)$。同理可以得到新的解 $(a,c,k(a+c)-b)$。

同样通过打表观察得到有一组解 $(1,k,k(k+1))$，这就是初始状态，从这个状态开始扩展即可。

使用 bfs 扩展和 set 判重，就可以 $O(n\log n)$ 解决本题，由于要高精度，代码实现使用 python。

k,n = map(int,input().split())
s = {0}
hd = 0
q = [(1,k,k*(k+1))]
while 1:
    a,b,c = q[hd]
    #print(a,b,c)
    if a<0 or b<0 or c<0:
        break
    hd = hd + 1
    if a not in s and b not in s and c not in s:
            print(a,b,c)
            s.add(a)
            s.add(b)
            s.add(c)
            n = n - 1
            if n == 0 :
                break
    q.append((b,c,k*(b+c)-a))
    q.append((a,c,k*(a+c)-b))
    tmp = k*(a+b)-c
    #if tmp>0 and tmp!=c :
    #    print("qwq")
    #    print(a,b,k*(a+b)-c)
    #    q.append((a,b,k*(a+b)-c))