[CERC2016] Easy Equations

Rainbow_qwq · 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))