AC代码

难度：简单,代码和思路在下面，仅供参考~😄 Difficulty:easy,code and ideas are here,for reference only~😄 ------>>>目录<<<------

• 思路1
• AC代码
• 彩蛋

1.思路1

先回顾一下九转大肠法~

例如，计算a=1071和b=462的最大公约数的过程如下：

(1)让1071除以462得到余数：147,所以gcd(1071,462)=gcd(462,147)

(2)让462除以147得到余数：21,所以gcd(462,147)= gcd(147,21)

(3)让47除以21得到余数：0,所以gcd(147,21)=gcd(21，0)

(4)此时较小的数已经是0，所以gcd(21，0)=21 所以gcd(1071,462)=21。

2.AC代码

#include <iostream>
using namespace std;
int m,n;
int gcd(int a,int b)
{
    if (b == 0)
    {
        return a;
    }
    return gcd(b,a % b);
}
int main()
{
    cin >> m >> n;
    cout << gcd(m,n);
    return 0;
}

貌似……万能的c++有个东西叫STL，STL里面又有个东西叫作__gcd(x,y)，用来求两个数的最大公约数啊！！！

所以……这道题就用十行不到的代码AC了……呵呵

贴代码

#include<bits/stdc++.h>
using namespace std;
int x,y;
int main(){
    cin>>x>>y;
    cout<<__gcd(x,y);//函数直接求最大公约数
    return 0;//完美AC~~
}

制作不易，麻烦给个赞再走呗~

#include<bits/stdc++.h>
using namespace std;
int n,m;
int gcd(int n,int m)
{
    if (m==0) return n;
    //在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零
    //这时，所剩下的还没有变成零的数就是两数的最大公约数
    return gcd(m,n%m);
    //两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数
    //用数学语言表示就是：gcd(a,b)=gcd（b，a%b)
}
int main()
{
    cin>>m>>n;
    cout<<gcd(n,m);//调用gcd函数
}

已AC，请放心食用。

编码不易,点赞走起~

记得点赞再抱走哦~

yasuo👀️ 这题不是做过吗

因为不论a和b的大小关系如何，b总是先等于0这句话我有点懵,不过我来解释一下

因为%每次取模后取模的该数会变为最小,又因为int gcd(int a,int b) 新a会继承b(最大) 新b会继承a%b(最小) 因此b始终是最小的,而且还是a(最大)%b(他自己) 就无需max min 找出大小

本人开始就用了max min👀️

希望对你有所帮助❤️

#include <iostream>
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);}
int main(){
    int n,m;std::cin>>n>>m;std::cout<<gcd(n,m);return 0;}

这道题不是很难，首先根据题目可以知道使用gcd(x,y)或者gcd（a,b）......都可以，然后判断终止条件就是逗号后面的变量== 0，的时候return前面的变量，总之代码如下！！描述有错误请大神指教！！第一次写题解请见谅啊啊啊！```

#include<bits/stdc++.h>
using namespace std;
int m,n;
int gcd(int x,int y)
{
if(y == 0)return x;
return gcd(y,x%y);
}
int main()
{
cin >> m >> n;
cout << gcd(m,n);
return 0;
}

具体步骤如上！

/*
#include<bits/stdc++.h>
#define gcd __gcd
using namespace std;
int main()
{
  int a,b;
  cin>>a>>b;
  cout<<gcd(a,b);
  return 0;
}*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b;
  cin>>a>>b;
  cout<<__gcd(a,b);
  return 0;
}
/*
#include<iostream>
using namespace std;
int gcd(int a,int b)
{return (b==0?a:gcd(b,a%b);}
int main()
{
    int n,m;
    cin >> n >> m;
    cout << gcd(n,m);
}



#include<iostream>
using namespace std;
int gcd(int a,int b)
{
  if(b==0) return a;
  else return gcd(b,a%b);
}
int main()
{
    int n,m;
    cin >> n >> m;
    cout << gcd(n,m);
}


#include<iostream>
using namespace std;
int gcd(int a,int b)
{
  while(b>0)
  {
    int r=a%b;
    a=b;b=r;
  }
  return a;
}
int main()
{
    int n,m;
    cin >> n >> m;
    cout << gcd(n,m);
}



#include<iostream>
using namespace std;
int gcd(int a,int b)
{
  for(int i=min(a,b);i>=1;i--)
    if(a%i==0&&b%i==0) return i;
}
int main()
{
    int n,m;
    cin >> n >> m;
    cout << gcd(n,m);
}
*/

推荐两种方法 1.用递归 2.用函数,已AC,请放心参考~ 建议自己先试一波在参考~

#include <bits/stdc++.h>//函数
using namespace std;
int x,y;//hetao2193769
int main()
{
    int x,y;
    cin>>x>>y;
    cout<<__gcd(x,y);
    return 0;
}
#include <bits/stdc++.h>//递归
using namespace std;
int func(int a,int b)
{
    if (b==0)
        return a;
    return func(b,a%b);
}
int main()
{
    int m,n;
    cin>>m>>n;
    cout<<func(m,n);
    return 0;
}

点赞拿走~

题意概括

输入a，b。求gcd(a,b)，即为a、b的最大公因数。

方法

gcd(a,b)=gcd(b,a%b)，可将一个问题变为一个更简单的子问题，可以用递归。且应课程所学，选择递归。

思路

递归的关键在于 递归公式 与 递归边界

1. 递归公式
   • 出题人非常的善良，直接给我们了：gcd(a,b)=gcd(b,a%b)。
   • 题目原话： 用数学语言表示就是：gcd(a,b)=gcd（b，a%b)
2. 递归边界

• 出题人也直接告诉我们了，这题太简单了：如果a0，则输出b，如果b0，这输出a。
• 题目原话：在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

代码+解析

#include <bits/stdc++.h>
using namespace std;
int a,b;
int gcd(int a,int b){
    if (a==0)  return b;
    else if (b==0)  return a;
    //递归边界。
    else  return gcd(b,a%b);
    //递归公式。
    //其实如果有0，那么一定是b，因为b一定是两数之中最小的
    //如果输入的b>a,那么gcd(b,a%b)=gcd(b,a)会直接交换。
}
int main()
{
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
}

#include <iostream>
using namespace std;
int m,n;
int gcd(int a,int b)
{
    if (b == 0)
    {
        return a;
    }
    return gcd(b,a % b);
}
int main()
{
    cin >> m >> n;
    cout << gcd(m,n);
    return 0;
}

题 解

还是十分简单，这里说下思路： 首先，规律已经在题目中给出，公式就是：函数名(最小的，最大的除以最小的的余数)，终止条件也很好找，也就是其中一项为零时，所以我们可以先用两个变量（minn和maxx，可以改）承载用min函数和max函数求得的最小值和最大值，然后判断最小值是否为零，如果为零就返回最大值，然后if外面就是刚刚所说的公式了。主函数内cin+cout+return 0;就可以了。 代码（AC已过，安心食用）：

#include<bits/stdc++.h>
using namespace std;
int m,n;
int gcd(int m,int n){
    int minn=min(m,n);
    int maxx=max(m,n);
    if(minn==0){
        return maxx;
    }
    return gcd(minn,maxx%minn);
}
int main(){
    cin>>m>>n;
    cout<<gcd(m,n);
    return 0;
}

本侠又来发题解啦，还是哪里不对请指出
（你们不会认为我会给一个没AC的吧）
#include<bits/stdc++.h>
using namespace std;
int m,n;
int gcd(int a,int b)
{
    if (b == 0)
    {
        return a;
    }
    return gcd(b,a % b);
}
int main()
{
    cin >> m >> n;
    cout << gcd(m,n);
    return 0;
}
感谢欧几里得，没有他就没有今天发题解的我。










































小彩蛋
一天小红去面试，人事经理问：“你想做什么工作？”小红说：“我想做人事经理。”然后她面试失败了······

本次题解已送达~（^_^）~

#include <bits/stdc++.h>
using namespace std;
int n, m;
int gcd(int x, int y)
{
	if (y == 0) return x;
	return gcd(y, x % y);
}
int main()
{
	cin >> n >> m;
	cout << gcd(n, m);
	return 0;
}

还挺简单的，就第一遍读题有点晕

int gcd(int m,int n)
{
    if (n == 0)
    {
        return m;
    }
    return gcd(n,m % n);
}

这是我的第一篇题解，代码不是很好，请多多指教😄😄😄 首先思路： 1.本题使用递归方法（辗转相除法），可以在函数gcd(a,b)中递归调用gcd(b,a%b)，不明白的可以在去回顾一下课程。 2.那终止条件是什么呢？应该是先判断若b==0,那就返回a。

AC代码

#include <bits/stdc++.h>
using namespace std;
int gcd(int n,int m)
{
    if (m == 0)//终止条件
    {
        return n;
    }
    return gcd(m,n % m);//递归语句
}
int main()
{
    int m,n;
    cin >> m >> n;//输入m,n
    cout << gcd(m,n)；//递归调用函数gcd
    return 0;
}

啦啦，本篇题解就结束了，记得点赞哦！👍

C2每课一题解（第一课 第二题）！！！

此题比前一题简单，也是需用此课的知识——递推就欧了。

递推是啥参见#P1001. 找规律

话不多说，上代码！

AC Code

#include<iostream>
using namespace std;
int n,m;
int gcd(int a,int b)
{
    if(b==0)//条件
    {
        return a;
    }
    return gcd(b,a%b);//公式(辗转相除法)。
}//简单的递推，照题上的写
int main()
{
    cin>>n>>m;
    cout<<gcd(n,m);
}

#include <iostream>//抽象已AC
#define _ int
#define ______ return
using namespace std;
_ m,n;
_ gcd(_ a,_ b)
{
    if (b == 0)
    {
        ______ a;
    }
    ______ gcd(b,a % b);
}
_ main()
{
    cin >> m >> n;
    cout << gcd(m,n);
    ______ 0;
}

本题目需要我们实现辗转相除法来求解两个整数的最大公约数。辗转相除法的原理为，两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。即：gcd(a, b) = gcd(b, a%b)。这个过程中，我们不断缩小较大的数直至其中一个变成零，最终得到的不为零的数就是两数的最大公约数。

解答过程：

根据题目描述，我们可以直接使用递归实现辗转相除法，代码如下：

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

上述代码中，如果b等于0，那么a就是最大公约数，直接返回a。否则，将b和a%b继续递归求解，直到b等于0。

在主函数中，我们需要读入两个整数n和m，并调用上述函数gcd求解它们的最大公约数。代码如下：

int main() {
    int n, m;
    cin >> n >> m;
    int result = gcd(n, m);
    cout << result << endl;
    return 0;
}

最后，输出最大公约数即可。

综上所述，本题目需要我们实现辗转相除法来求解两个整数的最大公约数。我们可以使用递归来实现辗转相除法，同时需要注意读入和输出的格式。

#include
using namespace std;
int m,n;
int gcd(int a,int b)
{
    if (b == 0)//如果b为0
    {
        return a;//返回a
    }
    return gcd(b,a % b);//递归调用gcd(b,a % b)
}
int main()
{
    cin >> m >> n;
    cout << gcd(m,n);//调用gcd(m,n)
    return 0;
}

这题比较简单，题干里讲的也比较明白所以咱就直接上代码：

int gcd(int a,int b)
{
    if (b == 0)//如果b是0就返回
        return a;
    return gcd(b,a % b);//否则就递归调用函数
}

这样做确实不错，为了保险，最好优化一下，方法自己想一下。 编写不易，点赞走起。

以AC

#include<bits/stdc++.h>
using namespace std;
int x,y;
int main(){
    cin>>x>>y;
    cout<<__gcd(x,y);
    return 0;
}