10814  Simplifying Fractions
Moderator: Board moderators

 New poster
 Posts: 15
 Joined: Sun Mar 07, 2004 7:47 pm
 Location: Moscow, Russia
10814  Simplifying Fractions
Hi!
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 64bit integers?
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 64bit integers?
Hello Pavel Nalivaiko.
MaxNumber for 64bit unsignt int is not bigger then 10^20 so you can't use it.I don't think that this problam can be solvable without using BigNumbers.I have solved this problem during the contest using my BigNumber calculations.If someone know other solution please tell.
Eduard
MaxNumber for 64bit unsignt int is not bigger then 10^20 so you can't use it.I don't think that this problam can be solvable without using BigNumbers.I have solved this problem during the contest using my BigNumber calculations.If someone know other solution please tell.
Eduard
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

 New poster
 Posts: 15
 Joined: Sun Mar 07, 2004 7:47 pm
 Location: Moscow, Russia
Hello, Eduard.
Sure, I know that 10**30 is greater then 2**64. But I mean, that we could represent our numbers as A*10**15+B, where A and B are Int64 numbers.
So, may be the implementation of BigNumbers using this representation is easier than implementation in general case?
I think that it's not fair to use in the contest code written before the contest starts  because you cant do in the real ACM ICPC competition.
So if there exist a way to simplify implementation, I just want to now how to do it.
Sure, I know that 10**30 is greater then 2**64. But I mean, that we could represent our numbers as A*10**15+B, where A and B are Int64 numbers.
So, may be the implementation of BigNumbers using this representation is easier than implementation in general case?
I think that it's not fair to use in the contest code written before the contest starts  because you cant do in the real ACM ICPC competition.
So if there exist a way to simplify implementation, I just want to now how to do it.
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.
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
im using the binary gcd (http://www.nist.gov/dads/HTML/binaryGCD.html) but it also is well above timelimit....
what else can i use?
and is bigint necessary to get the solution accepted here
what else can i use?
and is bigint necessary to get the solution accepted here
google

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
I have an open source big int implementation here:
http://www.lexansoft.com:8081/tools/
There is other stuff, too.
http://www.lexansoft.com:8081/tools/
There is other stuff, too.
If only I had as much free time as I did in college...

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
nukeu666:
The binaryGCD as described in the link can go into an endless loop for some values of u and/or v. Think about it, the cure is simple.
Suffers from this problem
The binaryGCD as described in the link can go into an endless loop for some values of u and/or v. Think about it, the cure is simple.
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;
}
 dovier_antonio
 New poster
 Posts: 47
 Joined: Fri Feb 18, 2005 5:00 am
 Location: Havana, Cuba
Hi Litle
I think that your algorithm looks so good!
Last edited by dovier_antonio on Fri Feb 03, 2012 9:21 am, edited 1 time in total.
Since inputs are not forthcoming...
I'll assume something is going awry in my scan input part which is as follows:
Any comments?
[edit]
That part is the root of all evil
[/edit]
Regards,
Suman.
I'll assume something is going awry in my scan input part which is as follows:
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';
[edit]
That part is the root of all evil
[/edit]
Regards,
Suman.
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.
Is that not the case ?
2 ^ 128 = 16 ^ 32 > 10 ^ 32 > 10 ^ 30 .
As noone here it talking about using builtin C++ types I guess
I am fundamentally wrong about that. But ... Isn't it true that
on 32bit 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 ?
One more thing. If I am right about these then how do
we read and print unsigned long long values. Actually even
long long should be anough if it can hold values up to
2 ^ 127  1 as we have :
2 ^ 127  1 == 8 . 16 . 2^120  1 == 8. 16 . 16^30  1 > 10 ^ 30
Is that not the case ?
I have tried using
scanf with %llu, %Lu for unsigned long long and
%lld, %Ld for long long, both don't work quite well. I mean
the value read is not okay if the number is 10^30.
Apparently long long and/or unsigned long long can not hold
such long integers , why is that ?
Then I tried printing with cout  this seems to work.
But reading the values with cin also does not work.
Any help is welcome.
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.
Is that not the case ?
2 ^ 128 = 16 ^ 32 > 10 ^ 32 > 10 ^ 30 .
As noone here it talking about using builtin C++ types I guess
I am fundamentally wrong about that. But ... Isn't it true that
on 32bit 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 ?
One more thing. If I am right about these then how do
we read and print unsigned long long values. Actually even
long long should be anough if it can hold values up to
2 ^ 127  1 as we have :
2 ^ 127  1 == 8 . 16 . 2^120  1 == 8. 16 . 16^30  1 > 10 ^ 30
Is that not the case ?
I have tried using
scanf with %llu, %Lu for unsigned long long and
%lld, %Ld for long long, both don't work quite well. I mean
the value read is not okay if the number is 10^30.
Apparently long long and/or unsigned long long can not hold
such long integers , why is that ?
Then I tried printing with cout  this seems to work.
But reading the values with cin also does not work.
Any help is welcome.
Abendego,
I took your C++ implementation of BigInt from
http://www.lexansoft.com:8081/tools/
and it works fine. The only thing I had to modify was to remove
the method which uses the operator >?= which is, as far
as I understood, a C++ extension supported only by
the g++ compiler. I think this operator was only used in
one following method :
BigInt operator* ( long double n );
Can someone point me to a reference of all these extensions ?!
I mean the extensions which g++ defines and supports.
I just don't have any other compiler than the one from
MS Visual Studio. Sorry if mentioning that would disturb you.
I am not a C++ expert at the end of the day. I am mostly using
Java as a programming language.
Thanks in advance.
I took your C++ implementation of BigInt from
http://www.lexansoft.com:8081/tools/
and it works fine. The only thing I had to modify was to remove
the method which uses the operator >?= which is, as far
as I understood, a C++ extension supported only by
the g++ compiler. I think this operator was only used in
one following method :
BigInt operator* ( long double n );
Can someone point me to a reference of all these extensions ?!
I mean the extensions which g++ defines and supports.
I just don't have any other compiler than the one from
MS Visual Studio. Sorry if mentioning that would disturb you.
I am not a C++ expert at the end of the day. I am mostly using
Java as a programming language.
Thanks in advance.

 Experienced poster
 Posts: 151
 Joined: Tue Nov 16, 2004 7:23 pm
 Location: Norway
 Contact:
The sizes you wrote above are incorrect. 32bit 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 builtin C++ types I guess
I am fundamentally wrong about that. But ... Isn't it true that
on 32bit 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]
int: 4 bytes
long: 4 bytes (Java uses 8 bytes, I think)
long long: 8 bytes