/*
DATE:3/11/2008
AUTHOR: M DEEPAK
MAIL BUGS TO:mdeepak@cse.iitk.ac.in
*/
/*
3. ) Consider the following formulations for GCD of two numbers. Use this formu-
lation carefully to design a compact recursive code for computing GCD of two numbers.
The value of n and m is provided from the command line.
 GCD(2m, 2n) = 2 * GCD(m, n)
 GCD(2m, 2n+1) = GCD(m, 2n+1)
 GCD(2m+1, 2n+1) = GCD(n-m, 2m+1) if m < n
 GCD(m, m) = m
*/
class GCD{
	
		public static void main(String args[]){
			
			int n=0;
			int m=0;
			
			try{				
				m=Integer.parseInt(args[0]);
				n=Integer.parseInt(args[1]);
			}catch(Exception e){
				
				System.out.println("Please Enter two numbers as argument");
				System.exit(0);
			}
			if(n==0||m==0){
			  System.out.println("The numbers entered, m="+m+",n="+n+" are not valid to find GCD");
			  System.exit(0);
			}

			System.out.println("GCD("+m+","+n+")="+gcd(m,n));
			
		}
		public static int gcd(int m,int n){
			
			if(m%2==0&&n%2==0)
				return 2*gcd(m/2,n/2);
				
			else if(m%2==0)
				return gcd(m/2,n);
			
			else if(n%2==0)
				return gcd(n/2,m);

			else if(n==m)
				return n;
				
		       else if(m<n)//both are odd
		    	return gcd((n/2)-(m/2),m);
		    
		      else
			return gcd((m/2)-(n/2),n);
		}
}