10892 - LCM Cardinality

[lonelyone]

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

[shamim]

Are you handling square numbers properly.

[Jan]

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.

[shamim]

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]

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]

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]

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

[Jan]

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...

[jdmetz]

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

[J&Jewel]

This problem can also be solved by the prime....solution...

[jdmetz]

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]

hi jdmetz,

can u please explain ur algorithm with prime solution?

[dreamvan]

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);
}

[Martin Macko]

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]

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

Code: Select all

code deleted.