不定方程求解

_hxh @ 2024-09-19 20:36:57

by _hxh @ 2024-09-19 21:01:08

@xyzqwq 问题就在于 c 不一定是完全平方数

by hutao_sdog @ 2024-09-19 21:03:49

对于一个二元一次方程 ax+by=c，若是有解，需要满足 c|gcd(a,b)。那么将两边同时除以 gcd(a,b)，此时 a 和 b 互质。用裴蜀定理求出 ax'+by'=1 的一组特解，从而求出原方程的一组特解 x_0=cx'，y_0=cy'。然后就可以求通解了

by hutao_sdog @ 2024-09-19 21:06:50

或者你可以看一下这个https://www.cnblogs.com/XP3301Pipi/p/18312749

by Joe2011 @ 2024-09-19 21:09:42

直接exgcd，注意到解出来可以枚举，直接 \log n 判断平方数

by _hxh @ 2024-09-19 21:17:39

@Joe2011 @hutao_sdog 哦，是不是通过 exgcd 求出 x,y 再选取 x,y 为完全平方数的解？

by Joe2011 @ 2024-09-19 21:19:49

@_hxh 大概是的，但是得看你 c 的范围

by lhz2022 @ 2024-09-19 21:22:01

@_hxh 枚举x 算出 ax^2 然后求解y^2=(c-ax^2)/b 但是你手算的话还是参考楼下大佬(毕竟c>10^4)

by _hxh @ 2024-09-19 21:22:22

@Joe2011 c 大概 10^4~10^5 的样子

by Joe2011 @ 2024-09-19 21:23:37

@_hxh 那么就是求一下非负整数的通解。。。我这儿还有代码呢。。。

by _hxh @ 2024-09-19 21:23:40

@lhz2022 @hutao_sdog @ScatteredHope @xyzqwq @Joe2011 感谢你们提出的解法，谢谢你们