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

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

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

【算法分析】 gcd(a,b)=gcd(b,a%b)gcd(a,b) = gcd(b,a\%b)gcd(a,b)=gcd(b,a%b)。 【参考代码】 【时间复杂度】 O(logn)O(logn)O(logn) 【预计得分】 100pts100pts100pts

include <bits/stdc++.h> using namespace std; int f(int a,int b) { if(a%b==0) return b; else return f(b,a%b); } int main() { int a,b; cin>>a>>b; cout<<f(a,b); return 0; }

__gcd()专门用来计算最大公约数

or or