题解 | #最大公约数#

最大公约数

http://www.nowcoder.com/practice/cf4091ca75ca47958182dae85369c82c

核心:gcb(a, b) = gcb(b, a%b)
证明:只要证明gcb(a, b) = gcb(b, a-b)即可
假设gcb(a, b) = c,证明分两步:

  • step 1:证明c是gcb(b, a-b)的公约数
    gcb(a,b) = c
    => a = k1*c, b = k2*c
    => a-b = (k1-k2)*c, 又b=k2*c
    => c是b和a-b的公约数
  • step 2:证明c是gcb(b, a-b)的最大公约数
    假设存在d>c且b=k3*d, a-b=k4*d
    => a = (k4-k3)*d, b = k3*d
    => 与c是a,b的最大公约数矛盾
    => c是b, a-b的最大公约数
    #
    # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
    #
    # 求出a、b的最大公约数。
    # @param a int 
    # @param b int 
    # @return int
    #
    class Solution:
      def gcd(self , a , b ):
          # write code here
          if a%b == 0:
              return b 
          else:
              return self.gcd(b, a%b)
    

```

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利 有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的 真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
07-02 13:52
门头沟学院 Java
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务