来自当知百科
跳转到: 导航搜索

  GCD是缩写,意义有多种。

目录

最大公约数

  最大公约数(greatestcommon divisor,简写为gcd;或highest commonfactor,简写为hcf),指某几个整数共有因子中最大的一个。

  例如,12和30的公约数有:1、2、3、6,其中6就是12和30的最大公约数。

  两个整数的最大公约数主要有两种寻找方法:

  * 两数各分解质因子,然后取出同样有的项乘起来

  * 辗转相除法(扩展版)

  和最小公倍数(lcm)的关系:gcd(a, b)×lcm(a, b) = ab

  两个整数的最大公因子可用于计算两数的最小公倍数,或分数化简成最简分数。

  两个整数的最大公因子和最小公倍数中存在分配律:

  * gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))

  * lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))

  在座标里,将点(0, 0)和(a, b)连起来,通过整数座标的点的数目(除了(0, 0)一点之外)就是gcd(a, b)。

  //GDC 分解因素法

  #include<iostream>

  using namespace std;

  int main()

  {

  int s,x,y,i;

  i=2;s=1;

  cin>>x,y;

  while(i<x)

  {

  if((x%i==0)&&(y%i==0))//i是其因子

  {s*=i;//符合条件的因子累积

  x/=i;

  y/=i;

  }

  else i=i+1;//测试试除数

  }

  cout<<"GCD is"<<s<<endl;

  return 0;

  }

  虽然可以 计算 但有时结果不是很理想

  //GDC 辗转相除法

  #include<iostream>

  using namespace std;

  int main()

  {

  int m,n,r;

  cin>>m,n;

  if(m<n)

  {int t;

  t=n;n=m;m=t;}

  else{

  do{

  r=m%n;

  m=n;

  n=r;

  }while(r);}

  cout<<"GCD is"<<m;

  return 0;

  }

  //work out gcd with sub

  #include <iostream>

  using namespace std;

  int main()

  {

  int x,y,a,b;

  cin>>x>>y;

  a=x;

  b=y;

  while(a!=b)

  if(a>b)

  a-=b;

  else

  b-=a;

  cout<<"Gcd is"<<a;

  return 0;

  }

  //递归法

  #include <iostream>

  using namespace std;

  int gcd(int x,int y)

  {int Gcd;

  if(x%y==0)

  Gcd=y;

  else

  Gcd=gcd(y,x%y);

  return Gcd;

  }

  int main()

  {

  int a,b;

  cin>>a>>b;

  cout<<"Gcd is the hope of our people"<<gcd(a,b);

  return 0;

  }

  #include <iostream>

  using namespace std;

  class Max_gcd

  {

  public:

  int gcd1(int m,int n);

  int gcd2(int m,int n);

  int gcd3(int m,int n);

  int gcd4(int m,int n);

  private:

  int m,n;

  };

  int Max_gcd::gcd1(int m,int n)

  {

  int d=1;

  for(int k=2;k<=m&&k<=n;k++)

  if(m%k==0&&n%k==0)

  d=k;

  return d;

  }

  int Max_gcd::gcd2(int m,int n)

  {

  int k;

  for(k=(m>n ? n:m);m%k!=0|n%k!=0;k--)

  ;

  return k;

  }

  int Max_gcd::gcd3(int m,int n)

  {

  int r;

  do{

  r=m%n;

  m=n;

  n=r;

  }while(r);

  return m;

  }

  int Max_gcd::gcd4(int m,int n)

  {

  int r;

  if(n==0) return m;

  for(r=m%n;r!=0;r=m%n)

  {

  m=n;

  n=r;

  }

  return n;

  }

  int main()

  {

  int x,y;

  int j=1;

  char choice;

  Max_gcd gcd;

  while(j)

  {

  cout<<"-----------------------------------------------"<<endl;

  cout<<" 多种方法求最大公约数:"<<endl;

  cout<<" 试除法求最大公约数a:"<<endl;

  cout<<" 从某个大数求最大公约数b:"<<endl;

  cout<<" 辗转相除法求最大公约数c:"<<endl;

  cout<<" 利用殴几里得算法和循环结构求最大公约数d:"<<endl;

  cout<<"------------------------------------------------"<<endl;

  cout<<"\t\t请选择菜单号(a--d):";

  cin>>choice;

  getchar();

  if(choice=='a')

  {

  cout<<"please input m,n:"<<endl;

  cin>>x>>y;

  cout<<gcd.gcd1(x,y)<<endl;

  }

  if(choice=='b')

  {

  cout<<"please input m,n:"<<endl;

  cin>>x>>y;

  cout<<gcd.gcd2(x,y)<<endl;

  }

  if(choice=='c')

  {

  cout<<"please input m,n:"<<endl;

  cin>>x>>y;

  cout<<gcd.gcd3(x,y)<<endl;

  }

  }

  if(choice=='d')

  {

  cout<<"please input m,n:"<<endl;

  cin>>x>>y;

  cout<<gcd.gcd4(x,y)<<endl;

  }

  return 0;

  }

共产党

  网上对“共产党”的拼音缩写。

  Gong Chan Dang

技能公共冷却时间

  《魔兽世界》中global cooldown 的缩写,即技能公共冷却时间。

创意群总监

  广告公司中 为Group Creative Director的缩写 即 创意群总监

游戏简称

  《鬼吹灯外传》这款游戏汉语拼音的简称。

个人工具
名字空间

变换
查看
操作
导航
工具箱