慈祥糖豆

文章
6
资源
0
加入时间
2年10月20天

【ICPC模板】多元一次不定方程(丢番图方程)求解

核心:首先移项,左边仅剩下ax + by,使用扩展欧几里得求解x和y,其右侧值应当满足能够整除gcd(a, b),接着用扩展gcd求解gcd(a, b)和c的参数,c的参数z将作为中间过程的答案,而gcd(a, b)的倍数将用来给前面求过的所有结果翻倍,以此类推。方程有解当且仅当右侧常数c能够整除gcd(a, b, c, d……)。代码:#include <iostream...