天天看点

nefu 630 Min Chain

题目:大意是说给定两个数,让你用这两个数,随意地进行+或者-两种操作,求出最小操作数使得结果为1,当不可能达到1的时候,输出-1.

方法:明显的数论题目,相当于求出ax+by=1的解。

           当两个数不互素时,得不到1的结果;

           当两个数互素时,使用拓展欧几里德来求得x和y,输出abs(x)+abs(y)-1即可。

注意:这道题目的数据涉及0、1,这些数据需要单独处理。

代码: