辗转相减求最大公约数(

#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; }

【算法分析】 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 a,b; int fun(int x,int y) { if(y==0) return x; return fun(y,x%y); } int main() { cin>>a>>b; cout<<fun(a,b); 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; }

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

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; }