题目描述 给出两个正整数A，B，求它们的最大公约数。
输入 第一行一个正整数A。 第二行一个正整数B。
输出 在第一行输出一个整数，表示A，B的最大公约数。
样例输入 18 24
样例输出 6
数据范围限制 在40%的数据中，1 ≤ A，B ≤ 10^6 在60%的数据中，1 ≤ A，B ≤ 10^18 在80%的数据中，1 ≤ A，B ≤ 10^100 在100%的数据中，1 ≤ A，B ≤ 10^1000 —————————————————————————— 这一题我一开始想到用辗转相除法+高精，结果超时 这题用辗转太慢了，所以涉及到一个伟大的算法——迭代 如果两个数为偶数 结果乘2，两个数分别除以2 如果一偶一奇，偶数除以2，奇数不变 如果两个奇数，大的减去小的，保留小的 如果用辗转，要用高精除以高精，这样肯定超时 如果用迭代，只需打高精除低精就好了 （原谅我变量名过于庸俗）
string gcd(string a,string b){//迭代 string p; if(a.size()<b.size()||(a.size()==b.size()&&a<b)) swap(a,b); if(a==b) return a; else if(ou(a)==0&&ou(b)==0) p=gcd(jian(a,b),b); else if(ou(a)==1&&ou(b)==0) p=gcd(chu(a,2),b); else if(ou(a)==0&&ou(b)==1) p=gcd(a,chu(b,2)); else p=cheng("2",gcd(chu(a,2),chu(b,2))); return p; }全部代码如下↓
#include<iostream> #include<string> #include<cstring> #include<cstdio> using namespace std; string A,B; int ou(string x){//判断偶数 if(x[x.size()-1]=='0'||x[x.size()-1]=='2'||x[x.size()-1]=='4'||x[x.size()-1]=='6'||x[x.size()-1]=='8') return 1; else return 0; } string chu(string a,int b){//高精除以低精 string jg1=""; int i,zs=0,jg; for(i=0;i<=a.size()-1;i++){ zs=zs*10+char(a[i]-48); jg=zs/b; jg1=jg1+char(jg+48); zs=zs%b; } while(jg1[0]=='0'&&jg1.size()>1) jg1.erase(0,1); return jg1; } string cheng(string a,string b){//高精乘 int l=0,a1[1001]={0},b1[1001]={0},c1[1001]={0},p,jw,i,j; string ans=""; for(i=1;i<=a.size();i++) a1[i]=int(a[a.size()-i]-48); for(i=1;i<=b.size();i++) b1[i]=int(b[b.size()-i]-48); for(i=1;i<=a.size();i++){ jw=0; for(j=1;j<=b.size();j++){ p=c1[i+j-1]; c1[i+j-1]=(c1[i+j-1]+a1[i]*b1[j]+jw)%10; jw=(p+a1[i]*b1[j]+jw)/10; } c1[j+i-1]+=jw; } l=i+j-2; while(c1[l]==0) l--; for(i=1;i<=l;i++) ans=char(c1[i]+48)+ans; return ans; } string jian(string a,string b){//高精减 string t,jg=""; int i,n=0,max=0,j,k,c=0,l,y=0,o=0; int a1[100001]={0},b1[100001]={0},c1[100001]={0}; if(a.size()<b.size()||(a.size()==b.size()&&a<b)){ t=a; a=b; b=t; o=1; } for(i=1;i<=a.size();i++) a1[i]=int(a[a.size()-i]-48); for(j=1;j<=b.size();j++) b1[j]=int(b[b.size()-j]-48); for(k=1;k<=i-1||k<=j-1;k++){ c1[k]=a1[k]-b1[k]; if(c1[k]<0){ c1[k]+=10; a1[k+1]--; } } if(o==1) jg="-"; while(c1[k-1]==0&&k!=2) k--; for(i=k-1;i>0;i--) jg=jg+char(c1[i]+48); return jg; } string gcd(string a,string b){//迭代 string p; if(a.size()<b.size()||(a.size()==b.size()&&a<b)) swap(a,b); if(a==b) return a; else if(ou(a)==0&&ou(b)==0) p=gcd(jian(a,b),b); else if(ou(a)==1&&ou(b)==0) p=gcd(chu(a,2),b); else if(ou(a)==0&&ou(b)==1) p=gcd(a,chu(b,2)); else p=cheng("2",gcd(chu(a,2),chu(b,2))); return p; } int main(){ freopen("gcd.in","r",stdin); freopen("gcd.out","w",stdout); cin>>A>>B; cout<<gcd(A,B); }