Posted on 2007-05-25 23:35
oyjpart 阅读(2672)
评论(6) 编辑 收藏 引用 所属分类:
ACM/ICPC或其他比赛
扩展欧几里德的基本用法如下
方程 ax + by = C
要求x，y~~的解或者通解
若a,b,c存在大于1公约数 可以把这三个系数同时除掉公约数
此时如GCD(a, b)不整除C 则无解 因为两边同时除以GCD(a, b) 左边是整数 右边是小数 矛盾~
若整除 则除以GCD(a, b)得到新的 ax + by = k
若k 等于 1; 则用 extend_Eulid求解x，y
若k不等于1； 求解ax + by = 1 用extend-Eclude求出来之后乘以k即可
POJ上面的2个练习题：
PKU1061 青蛙的约会：扩展欧几里德
跳蚤：最大公约数为1一定能导致同余1方程有解 再用m的因式分解判断前面的数是否都含有这个因式