Discrete Math

This is a discussion on Discrete Math within the C Programming forums, part of the General Programming Boards category; I know that this isn't a math forum .. but i have always found help here so i am posting ...

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    Discrete Math

    I know that this isn't a math forum .. but i have always found help here so i am posting something again

    Given:
    Code:
    N  ,  M  ,  K  ,  gcd(a,b)=1
    
    N,M can be written as
    N = a + b
    M = a^2 + b^2 - (2^K - 2) * a * b
    
    Note: a,b are not given
    N ,M ~ 10^400
    Find gcd(N,M)

    Now for this i write a brute force code and i always get gcd as a power of two
    i.e
    gcd(N,M)=2^z

    Hence for finding gcd i use a loop each time multiplying the gcd by 2 and checking if( N%gcd==0 && M%gcd===0 )
    But this still ain't fast enough !

    Is there any way to compute the gcd faster ??

    Thanks

  2. #2
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    Are gcd's always powers of any other numbers? 4? 8? 16? 32?
    Do a log to the base 4/16 etc over all the gcd elements and see if you get whole number results.

  3. #3
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    Re

    I dont know what u meant but this is my current code
    Code:
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    bool mod(const char *str,int num) //check if str%num==0
    {
    	int i,len=strlen(str),res=0;
    	
    	for(i=0;i<len;i++)
    	{
    		res=10*res+str[i]-'0';
    		res%=num;
    	}
    	return res==0;
    }
    
    int main()
    {
    	int cases,K,gcd,temp;
    	char N[1005],M[1005];
    	
    	
    	scanf("%d",&cases);
    	while(cases--)
    	{
    		scanf("%s %s %d",N,M,&K);
    		
    		gcd=1;
    		temp=1;
    		
    		while(1)
    		{
    			if(mod(N,temp) && mod(M,temp))gcd=temp;
    			else break;	
    			temp*=2;
    		}
    		printf("%d\n",gcd);
    	}
    	return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Math
    By knightjp in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 04-01-2009, 05:36 PM
  2. Basic Math Problem. Undefined Math Functions
    By gsoft in forum C Programming
    Replies: 1
    Last Post: 12-28-2004, 02:14 AM
  3. Discrete Math question
    By theoddmonkey in forum Tech Board
    Replies: 2
    Last Post: 07-01-2004, 08:41 AM
  4. toughest math course
    By axon in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 10-28-2003, 09:06 PM
  5. Discrete Math
    By rickc77 in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 02-19-2002, 10:43 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21