poj1061

你的名字 2021-12-14 00:07 150阅读 0赞

构造方程 (x + m \* s) - (y + n \* s) = k \* l(k = 0, 1, 2,...)

变形为 (n-m) \* s + k \* l = x - y。即转化为模板题，a \* x + b \* y = n，是否存在整数解。

<table> 
 <tbody> 
 <tr> 
 <td> 
 <div style="line-height:20px;color:#d0d0d0;font-size:14px;border:#999999 1px solid;"> 
 #include&nbsp;&lt;iostream&gt; using&nbsp;namespace&nbsp;std; #define&nbsp;LL&nbsp;long&nbsp;long LL&nbsp;gcd(LL&nbsp;a,&nbsp;LL&nbsp;b) { &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;b&nbsp;?&nbsp;gcd(b,&nbsp;a%b)&nbsp;:&nbsp;a; } //find&nbsp;x,&nbsp;y&nbsp;that&nbsp;satisfied&nbsp;the&nbsp;equation&nbsp;ax+by=d,&nbsp;which&nbsp;minimize&nbsp;the&nbsp;{|x|+|y|}.&nbsp;ps:d&nbsp;=&nbsp;gcd(a,b). void&nbsp;exgcd(LL&nbsp;a,&nbsp;LL&nbsp;b,&nbsp;LL&nbsp;&amp;d,&nbsp;LL&nbsp;&amp;x,&nbsp;LL&nbsp;&amp;y) { &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!b) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d&nbsp;=&nbsp;a,&nbsp;x&nbsp;=&nbsp;1,&nbsp;y&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;exgcd(b,&nbsp;a&nbsp;%b,&nbsp;d,&nbsp;y,&nbsp;x); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;y&nbsp;-=&nbsp;x&nbsp;*&nbsp;(a&nbsp;/&nbsp;b); &nbsp;&nbsp;&nbsp;&nbsp;} } //1、先计算Gcd(a,&nbsp;b)，若n不能被Gcd(a,&nbsp;b)整除，则方程无整数解；否则，在方程两边同时除以Gcd(a,&nbsp;b)，得到新的不定方程a'&nbsp;*&nbsp;x&nbsp;+&nbsp;b'&nbsp;*&nbsp;y&nbsp;=&nbsp;n'，此时Gcd(a',&nbsp;b')=1; //2、利用上面所说的欧几里德算法求出方程a'&nbsp;*&nbsp;x&nbsp;+&nbsp;b'&nbsp;*&nbsp;y&nbsp;=&nbsp;1的一组整数解x0,&nbsp;y0，则n'&nbsp;*&nbsp;x0,n'&nbsp;*&nbsp;y0是方程a'&nbsp;*&nbsp;x&nbsp;+&nbsp;b'&nbsp;*&nbsp;y&nbsp;=&nbsp;n'的一组整数解； //3、根据数论中的相关定理，可得方程a'&nbsp;*&nbsp;x&nbsp;+&nbsp;b'&nbsp;*&nbsp;y&nbsp;=&nbsp;n'的所有整数解为： //x&nbsp;=&nbsp;n'&nbsp;*&nbsp;x0&nbsp;+&nbsp;b'&nbsp;*&nbsp;t //y&nbsp;=&nbsp;n'&nbsp;*&nbsp;y0&nbsp;-&nbsp;a'&nbsp;*&nbsp;t //(t为整数) bool&nbsp;getans(LL&nbsp;a,&nbsp;LL&nbsp;b,&nbsp;LL&nbsp;c,&nbsp;LL&nbsp;&amp;ans)//&nbsp;ax&nbsp;+&nbsp;by&nbsp;=&nbsp;c&nbsp;最小整数解 { &nbsp;&nbsp;&nbsp;&nbsp;LL&nbsp;r&nbsp;=&nbsp;gcd(a,&nbsp;b),&nbsp;y0; &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(c%r)//no&nbsp;solutions &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;a&nbsp;/=&nbsp;r,&nbsp;b&nbsp;/=&nbsp;r,&nbsp;c&nbsp;/=&nbsp;r; &nbsp;&nbsp;&nbsp;&nbsp;exgcd(a,&nbsp;b,&nbsp;r,&nbsp;ans,&nbsp;y0);//至此，上面的说明解决了 &nbsp;&nbsp;&nbsp;&nbsp;LL&nbsp;t&nbsp;=&nbsp;c&nbsp;*&nbsp;ans&nbsp;/&nbsp;b; &nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;=&nbsp;c&nbsp;*&nbsp;ans&nbsp;-&nbsp;t&nbsp;*&nbsp;b; &nbsp;&nbsp;&nbsp;&nbsp;/*此时方程的所有解为：x&nbsp;=&nbsp;c*ans&nbsp;-&nbsp;b*t,&nbsp;x的最小的可能值是0 &nbsp;&nbsp;&nbsp;&nbsp;令x&nbsp;=&nbsp;0可求出当x最小时的t的取值，但由于x&nbsp;=&nbsp;0是可能的最小取值，实际上可能x根本取不到0 &nbsp;&nbsp;&nbsp;&nbsp;那么由计算机的取整除法可知：由&nbsp;t&nbsp;=&nbsp;c*k1&nbsp;/&nbsp;b算出的t &nbsp;&nbsp;&nbsp;&nbsp;代回x&nbsp;=&nbsp;c*ans&nbsp;-&nbsp;b*t中，求出的x可能会小于0，此时令t&nbsp;=&nbsp;t&nbsp;+&nbsp;1，求出的x必大于0； &nbsp;&nbsp;&nbsp;&nbsp;如果代回后x仍是大于等于0的，那么不需要再做修正。*/ &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(ans&nbsp;&lt;&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;+=&nbsp;b; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true; } int&nbsp;main() { &nbsp;&nbsp;&nbsp;&nbsp;LL&nbsp;x,&nbsp;y,&nbsp;m,&nbsp;n,&nbsp;L; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(cin&nbsp;&gt;&gt;&nbsp;x&nbsp;&gt;&gt;&nbsp;y&nbsp;&gt;&gt;&nbsp;m&nbsp;&gt;&gt;&nbsp;n&nbsp;&gt;&gt;&nbsp;L) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LL&nbsp;a&nbsp;=&nbsp;n&nbsp;-&nbsp;m,&nbsp;b&nbsp;=&nbsp;L,&nbsp;c&nbsp;=&nbsp;x&nbsp;-&nbsp;y; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LL&nbsp;ans; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bool&nbsp;flag&nbsp;=&nbsp;getans(a,&nbsp;b,&nbsp;c,&nbsp;ans); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!flag) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;"Impossible"&nbsp;&lt;&lt;&nbsp;endl; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;ans&nbsp;&lt;&lt;&nbsp;endl; &nbsp;&nbsp;&nbsp;&nbsp;} } 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

转载于:https://www.cnblogs.com/james1207/p/3318191.html