Ai+Bj+Ck=X

发布时间 2023-08-21 11:39:37作者: wscqwq

G - Ai + Bj + Ck = X (1 <= i, j, k <= N)

考虑 \(n\) 的范围,枚举 \(i\)

于是就转换成求解 \(Bj+Ck=X-Ai\)

这是一个扩展欧几里得的典型应用,可以求 \(Bj+Ck=\gcd(B,C)\) 的一组解。而且左边的式子始终一样,所以只需求解一遍。

首先判断右边是否是 \(\gcd\) 的倍数,如果是的话就就将解扩大 \((X-Ai)\div\gcd\)

根据 \(ax+by=\gcd(a,b)\) 的所有解的公式:

\(x=x_0-k\dfrac{b}{d},y=y_0+k\dfrac{a}{d}\)\(k\) 为负亦可,下面将左边的当作加,右边的当作减)。

将最小的 \(x\) 对应的解求出。

然后再根据上面的 \(x\) 变成最小的在范围内的数,然后若 \(y\) 也在范围内,那么计算二者每次递增、递减超出边界的最少次数即可。

注意取模,防止爆 long long

AC