9도 노트의 최대 공약수

631 단어
를 참고하여 나머지를 직접 활용하면 특히 큰 숫자에 대한 계산량이 크고 전전상감의 귀속 속도가 너무 느리기 때문에 아래의 방법으로 aint gcd(int a,int b){ if(a==b) return a; if(a<b){ return gcd(b,a); } if(a&1){//a if(b&1){ return gcd(a-b,b); }else{ return gcd(a,b>>1); } }else{//a if(b&1){ return gcd(a>>1,b); }else{ return 2*gcd(a>>1,b>>1); } } } void test1056(){ int a; int b; while(std::cin>>a>>b){ std::cout<<gcd(a,b)<<std::endl; } }

좋은 웹페이지 즐겨찾기