hdu 2669 Romantic (扩展欧几里得模板题)

题目链接

题意:问a*x+b*y=1的一组x>0的解,如果无解输出sorry.

思路:根据裴蜀定理, a*x+b*y=1有解当且gcd(a,b)=1。

然后根据扩展欧几里得算法,我们可以得到一组x,y。需要注意的是,这只是其中一组解。

x,y的通解为:(x+k*gx , y-k*gy ) 其中:gx= b/gcd(a,b),gy = a/gcd(a,b),k为任意整数 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz