求最大公约数的Stein算法以及高精度实现求最大公约数的Stein算法以及高精度实现

现在的位置: 首页 > 综合 > 正文

求最大公约数的Stein算法以及高精度实现求最大公约数的Stein算法以及高精度实现

2017年11月04日 ⁄ 综合 ⁄ 共 984字 ⁄ 字号小中大 ⁄ 评论关闭

求最大公约数的Stein算法以及高精度实现

分类：数论2013-04-07
12:47 59人阅读评论(0) 收藏举报

首先来介绍一下什么是Stein算法：

[cpp]view

 plaincopy

#include <iostream>  

using namespace std;  

int abs(int x)  

{  

    return x>0? x:-x;  

}  

int gcd(int a,int b)  

{  

    if(a==0) return b;  

    if(b==0) return a;  

    if(a%2==0&&b%2==0)   return 2*gcd(a/2,b/2);  

    else if(a%2==0)      return gcd(a/2,b);  

    else if(b%2==0)      return gcd(a,b/2);  

    else                 return gcd(abs(a-b),min(a,b));  

}  

int main()  

{  

    int a,b;  

    while(cin>>a>>b)  

    {  

        cout<<gcd(a,b)<<endl;  

    }  

    return 0;  

}

题目：高精度GCD

Java代码：

[cpp]view

 plaincopy

import java.util.*;  

import java.math.BigInteger;  

public class Main  

{  

      public static void main(String[] args)  

      {  

            Scanner cin = new Scanner(System.in) ;  

            BigInteger a =cin.nextBigInteger();  

            BigInteger b =cin.nextBigInteger();  

            BigInteger ans=a.gcd(b);  

            System.out.println(ans);  

      }  

}