2 条题解
-
1
col1 col2 col3 变换：px-qy=b-a 令-y=h px1+qy1=b-a 对应整数对(x1,y1) 由扩展欧几里得，得 px2+qy2=gcd(p,q) 对应整数对(x2,y2) 且 x1,y1为整数 所以 如果 b-a=k*gcd(p,q) 保证可以有解 这是充分不必要的 那么怎么证明必要性呢 我们知道如果这个方程成立 还有一种情况即 gcd(p,q)*k+dx*p-dy*q但是我们在求解gcd(p,q)的时候，如果采用二进制会在递推中产生迭代 return gcd(a-b,b)那么只有迭代次数足够多 我们总是有 gcd(a,b)->gcd(a-b,b)->gcd(dx*a-dy *b,b) (这里可以说是应用了一下更相减损) 于是我们所求得的，一定是最优解，必要性得到证明 证毕