10892  LCM Cardinality
Moderator: Board moderators
10892  LCM Cardinality
Could someone give me some tricky input.
Appreciate you. ^^
Appreciate you. ^^
Try the following input output set...
Input:
Output:
Hope it works.
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
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
Last edited by Jan on Wed Aug 10, 2005 7:20 am, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage
HomePage
If you are getting WA, check your LCM calculating method.
Improper implementation can result in overflow.
It should be:
and not :
Improper implementation can result in overflow.
It should be:
Code: Select all
LCM(int x,int y) {
return x/GCD(x,y) * y;
}
Code: Select all
LCM(int x,int y) {
return x*y/GCD(x,y);
}

 New poster
 Posts: 8
 Joined: Thu Jul 15, 2004 3:52 pm
 Location: Russia, Cherepovets
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?
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?
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
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...
Thanks jdmetz for pointing that. I have changed the output...
Ami ekhono shopno dekhi...
HomePage
HomePage
Some trickier input
Input:Output:
Code: Select all
1073741824
446185740
892371480
1784742960
1338557220
4656960
Code: Select all
1073741824 31
446185740 16403
892371480 22964
1784742960 29525
1338557220 27338
4656960 2048
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.J&Jewel wrote:This problem can also be solved by the prime....solution...
10892
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[count1]==b[count1]) 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<count1;i++)
{
if(lcm(a,a[count1])==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);
}
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[count1]==b[count1]) 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<count1;i++)
{
if(lcm(a,a[count1])==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);
}

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: 10892
Actually, your code doesn't solve the sample input on my computer. It may be caused by these warnings:dreamvan wrote:Who can help me >< ....
Although I can deal with the sample input, I got WA.
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
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.
10892why WA need i/o
it seems all right.but got WA.
Can anyone help?
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.
Shahadat Hossain Sohag
CSEBUET0405089
http://sites.google.com/site/sohagbuetcse/
http://acm.uva.es/problemset/usersjudge.php?user=4428
CSEBUET0405089
http://sites.google.com/site/sohagbuetcse/
http://acm.uva.es/problemset/usersjudge.php?user=4428