可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。
——《九章算术》
#include <iostream> #include <cmath> using namespace std; int main() { int a,b,t,g,c=0; cin >> a >> b; while(a%2==0 && b%2==0) { a=a/2; b=b/2; c++; } do { if(a<b) swap(a,b); t=a-b; a=b; b=t; }while(a!=b); g=b*pow(2,c); cout << g << " "; }