
If there exist a simple way to solve this problem
(without writing classic "long arithmetics" )?
May be we could use that P,Q < 10**30, so both of them could be represented as a pair of two 64-bit integers?
Moderator: Board moderators
If there exists I want to know about it too.So if there exist a way to simplify implementation, I just want to now how to do it.
Code: Select all
int gcd(int u, int v){
int g=1;
while((u%2==0)&&(v%2==0)){
u/=2;
v/=2;
g*=2;
}
while(u>0){
if(u%2==0) u/=2;
else if(v%2==0) v/=2;
else if(u>=v) u-=v;
else v-=u;
}
return g*v;
}
Code: Select all
scanf("%d", &n);
getchar();
while ( n-- )
{
/* read somthing like dddd[ ]/[ ]dddd from the command line*/
fgets(buf, 1024, stdin);
k = i = 0;
while( !isdigit(buf[k]) ) k++;
while ( isdigit(buf[k]) )
{
num[i++] = buf[k];
k++;
}
num[i] = '\0';
i = 0;
while( !isdigit(buf[k]) ) k++;
/*skip the `/' */
while ( isdigit(buf[k]) )
{
den[i++] = buf[k++];
}
den[i] = '\0';
The sizes you wrote above are incorrect. 32-bit machines usually have (in C/C++):Sedefcho wrote:Isn't the C++ type unsigned long long enough for
this problem. If I am not completely wrong then
unsigned long long can hold values up to
2 ^ 128 - 1 which is much more than 10 ^ 30.
[snip]
As noone here it talking about using built-in C++ types I guess
I am fundamentally wrong about that. But ... Isn't it true that
on 32-bit machines we have:
size of INT is 4 bytes - 32 bits;
size of LONG is 8 bytes - 64 bits;
size of LONG LONG is 16 bytes - 128 bits ?
[snip]