10892 - LCM Cardinality

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

10892 - LCM Cardinality

Post by lonelyone » Tue Aug 09, 2005 7:44 am

Could someone give me some tricky input.
Appreciate you. ^^

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Aug 09, 2005 8:07 am

Are you handling square numbers properly.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Aug 09, 2005 2:10 pm

Try the following input output set...

Input:

Code: Select all

2
12
1000000
12345676
87675612
1251562
9412
6537
123
12
3244
56342
1233
344333
98123
1
2
3
243
123999
0
Output:

Code: Select all

2 2 
12 8 
1000000 85 
12345676 68 
87675612 23 
1251562 41 
9412 23 
6537 5 
123 5 
12 8 
3244 8 
56342 41 
1233 8 
344333 14 
98123 2 
1 1 
2 2 
3 2 
243 6 
123999 5
Hope it works.
Last edited by Jan on Wed Aug 10, 2005 7:20 am, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Aug 09, 2005 2:37 pm

If you are getting WA, check your LCM calculating method.
Improper implementation can result in overflow.

It should be:

Code: Select all

LCM(int x,int y) {
 return x/GCD(x,y) * y;
}
and not :

Code: Select all

LCM(int x,int y) {
 return x*y/GCD(x,y);
}

Andrey Grigorov
New poster
Posts: 8
Joined: Thu Jul 15, 2004 3:52 pm
Location: Russia, Cherepovets

Post by Andrey Grigorov » Tue Aug 09, 2005 4:22 pm

For N = 87675612 my program return LCM Cardinality = 23;
There are all pairs what program found:
(1,87675612) (2,87675612) (3,29225204) (3,87675612) (4,21918903) (4,43837806) (4,87675612) (6,29225204) (6,87675612) (12,7306301) (12,14612602) (12,21918903) (12,29225204) (12,43837806) (12,87675612) (7306301,87675612) (14612602,87675612) (21918903,29225204) (21918903,87675612) (29225204,43837806) (29225204,87675612) (43837806,87675612) (87675612,87675612)
Where is mistake? :(

jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA

Post by jdmetz » Tue Aug 09, 2005 4:29 pm

I think the output given above is wrong. Here is the output for that input from my AC program:

Code: Select all

2 2
12 8
1000000 85
12345676 68
87675612 23
1251562 41
9412 23
6537 5
123 5
12 8
3244 8
56342 41
1233 8
344333 14
98123 2
1 1
2 2
3 2
243 6
123999 5

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Tue Aug 09, 2005 5:26 pm

thanks for all, I got accept already.
I make an overflow on LCM computation.
thanks Shamim

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Aug 10, 2005 7:16 am

OOps sorry about that. Actually I used long long to calculate, but my compilar version doesnot support long long.

Thanks jdmetz for pointing that. I have changed the output...
Ami ekhono shopno dekhi...
HomePage

jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA

Some trickier input

Post by jdmetz » Wed Aug 10, 2005 4:22 pm

Input:

Code: Select all

1073741824
446185740
892371480
1784742960
1338557220
4656960
Output:

Code: Select all

1073741824 31
446185740 16403
892371480 22964
1784742960 29525
1338557220 27338
4656960 2048

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Post by J&Jewel » Fri Aug 12, 2005 12:14 pm

This problem can also be solved by the prime....solution...
I hate Wrong Answer!

jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA

Post by jdmetz » Fri Aug 12, 2005 2:12 pm

J&Jewel wrote:This problem can also be solved by the prime....solution...
Yes - the method I used, I don't even keep track of the prime factors. I just count how many of each one and compute the answer as I factor the number. That got me down to .004 seconds. To get to .002, I had to do my own input and output parsing.

inproblem
New poster
Posts: 4
Joined: Fri Oct 29, 2004 9:52 pm

Post by inproblem » Wed Aug 17, 2005 7:15 pm

hi jdmetz,

can u please explain ur algorithm with prime solution?

dreamvan
New poster
Posts: 2
Joined: Sat Sep 24, 2005 10:56 am

10892

Post by dreamvan » Sat Sep 24, 2005 11:03 am

Who can help me >< ....
Although I can deal with the sample input, I got WA.


**************************************

#include <stdio.h>
#include <math.h>

long int lcm(long int,long int);

int main()
{
long int count=0,d=0,i=0,total=0,half=0;
long int a[10000],b[10000];

while(1)
{
total=0;
count=0;
scanf("%d",&d);
if(d != 0)
{
for(i=2;i<=sqrt(d);i++)
{
if(d%i == 0)
{
a[count]=i;
b[count]=d/i;
count++;
total+=2;
}
}
if(a[count-1]==b[count-1]) total--;

for(i=0;i<count;i++)
{
a[count+i]=b;
}
count=count*2;
total+=2;
half=count/2;
for(;count>=half;count--)
{
for(i=0;i<count-1;i++)
{
if(lcm(a,a[count-1])==d)
{
total++;
}
}
}

if(d==1) printf("1 1\n");
else printf("%d %d\n",d,total);
}
else break;
}
return 0;
}

long int lcm(long int a,long int b)
{
long int t,i;

t=a*b;
if(a<b) a^=b^=a^=b;
while(b!=0)
{
i=a%b;
a=b;
b=i;
}

return(t/a);
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10892

Post by Martin Macko » Sat Sep 24, 2005 10:37 pm

dreamvan wrote:Who can help me >< ....
Although I can deal with the sample input, I got WA.
Actually, your code doesn't solve the sample input on my computer. It may be caused by these warnings:

Code: Select all

foo.c: In function `main':
foo.c:15: warning: int format, long int arg (arg 2)
foo.c:32: warning: assignment makes integer from pointer without a cast
foo.c:49: warning: int format, long int arg (arg 2)
foo.c:49: warning: int format, long int arg (arg 3)
foo.c: In function `lcm':
foo.c:61: warning: operation on `a' may be undefined
BTW, in future, please, put the posted code into

Code: Select all

 tags to make it more readable. And also do not create a new topic if there are already few on the problem.

sohag144
New poster
Posts: 14
Joined: Mon Feb 27, 2006 4:12 pm
Location: Dhaka,Bangladesh
Contact:

10892why WA need i/o

Post by sohag144 » Thu Jun 29, 2006 2:42 pm

it seems all right.but got WA.
Can anyone help?

Code: Select all

code deleted.
Last edited by sohag144 on Thu Jun 29, 2006 6:27 pm, edited 1 time in total.

Post Reply

Return to “Volume 108 (10800-10899)”