题解分享
题解分享简介
最大公约数 - 题解
```
/*
思路
思路一(error) 效率太低无法通过：
1. 循环从1到最小的那个数
2. 循环操作： if（a % i == 0 && b % i == 0)
3. 用max记录并更新
思路二（学习）：欧几里得法
1. 写一个gcd函数
2. 原理：两个数的最大公约数等于其中较小的数和两数相除的余数的最大公约数
3. gcd(a,b) = gcd(b,a%b)
*/
#include <bits/stdc++.h>
using namespace std;
long gcd( long a, long b ) {
while ( b != 0 ) {
//gcd(a,b) = gcd(b,a%b)
long temp = b;
b = a % b;
a = temp;
}
return a;
}
int main()
{
long a,b;
cin >> a >> b;
if ( a >= b ) {
cout << gcd(a,b) << endl;
} else {
cout << gcd(b,a) << endl;
}
return 0;
}
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
long m,n;
cin >> m >> n;
long min = 0;
if (m > n) min = n;
else min = m;
long max = 1;
for ( int i = 1; i <= min; i++ ) {
if ( m % i == 0 && n % i == 0 ) {
max = max < i ? i : max;
}
}
cout << max << endl;
return 0;
}
*/
```
查看全文
0
0
0
6
最大公约数 - 题解
```cpp
// https://dashoj.com/p/92
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
if(b == 0) return a;
return gcd(b, a % b);
}
int main() {
ll a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
return 0;
}
```
查看全文
0
0
0
2
最大公约数 - 题解
```
#include
#define int long long
using namespace std;
int gcd(int a,int b){
if(b==0){
return a;
}else{
return gcd(b,a%b);
}
}
signed main()
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b);
return 0;
}
```
0
0
0
2
最大公约数 - 题解
include
using namespace std;
using ll =long long;
ll gcd (ll a,ll b){
if(b==0){
return a;
}
return gcd (b,a%b);
}
int main(){
ll a,b; //主函数力还得定义
cin>>a>>b;
cout<< gcd(a,b) <<endl;
return 0;
}
查看全文
0
0
0
1
最大公约数 - 题解
oi-wiki
```cpp
#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
ll fxxk(ll a, ll b) {
return b == 0 ? a : fxxk(b, a % b);
}
int main() {
ll a, b;
cin >> a >> b;
cout << fxxk(a, b) << '\n';
return 0;
}
```
查看全文
0
0
0
1
