题目:大意是说给定两个数,让你用这两个数,随意地进行+或者-两种操作,求出最小操作数使得结果为1,当不可能达到1的时候,输出-1.
方法:明显的数论题目,相当于求出ax+by=1的解。
当两个数不互素时,得不到1的结果;
当两个数互素时,使用拓展欧几里德来求得x和y,输出abs(x)+abs(y)-1即可。
注意:这道题目的数据涉及0、1,这些数据需要单独处理。
代码:
题目:大意是说给定两个数,让你用这两个数,随意地进行+或者-两种操作,求出最小操作数使得结果为1,当不可能达到1的时候,输出-1.
方法:明显的数论题目,相当于求出ax+by=1的解。
当两个数不互素时,得不到1的结果;
当两个数互素时,使用拓展欧几里德来求得x和y,输出abs(x)+abs(y)-1即可。
注意:这道题目的数据涉及0、1,这些数据需要单独处理。
代码: