Thread: 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

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.

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;
}