# 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. ## 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. 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. ## 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;
}```