You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
|
|
#include<iostream>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
|
|
|
|
|
|
//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|
|
|
|
|
int gcd(int a,int b)
|
|
|
|
|
|
{
|
|
|
|
|
|
int ans=a>b? b:a;
|
|
|
|
|
|
while(ans>1&&(a%ans!=0||b%ans!=0))
|
|
|
|
|
|
{
|
|
|
|
|
|
ans--;
|
|
|
|
|
|
}
|
|
|
|
|
|
return ans;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
//շת<D5B7><D7AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|
|
|
|
|
//<2F><><EFBFBD><EFBFBD>a>b,<2C><><EFBFBD><EFBFBD>a<EFBFBD><61><EFBFBD>ܱ<EFBFBD>b<EFBFBD><62><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>b<EFBFBD><62>ֵ<EFBFBD><D6B5>a<EFBFBD><61><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵ<EFBFBD><D6B5>b<EFBFBD><62><EFBFBD>ظ<EFBFBD>ִ<EFBFBD><D6B4>a%b,ֱ<><D6B1>a<EFBFBD>ܹ<EFBFBD><DCB9><EFBFBD>b<EFBFBD><62><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʱ<EFBFBD><CAB1><EFBFBD><EFBFBD>b<EFBFBD><62>ֵ<EFBFBD><D6B5><EFBFBD><EFBFBD>Ϊ<EFBFBD><CEAA><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Լ<EFBFBD><D4BC><EFBFBD><EFBFBD>
|
|
|
|
|
|
int gcd2(int a,int b)
|
|
|
|
|
|
{ int c;
|
|
|
|
|
|
if(a<b)
|
|
|
|
|
|
{ a=a+b;
|
|
|
|
|
|
b=a-b;
|
|
|
|
|
|
a=a-b;
|
|
|
|
|
|
}
|
|
|
|
|
|
c=a%b;
|
|
|
|
|
|
while(a%b!=0)
|
|
|
|
|
|
{ a=b;
|
|
|
|
|
|
b=c;
|
|
|
|
|
|
c=a%b;
|
|
|
|
|
|
}
|
|
|
|
|
|
return b;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
int a,b;
|
|
|
|
|
|
cin>>a>>b;
|
|
|
|
|
|
cout<<gcd(a,b)<<endl;
|
|
|
|
|
|
cout<<gcd2(a,b)<<endl;
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
