### 10892 - LCM Cardinality

Posted:

**Tue Aug 09, 2005 7:44 am**Could someone give me some tricky input.

Appreciate you. ^^

Appreciate you. ^^

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=30&t=11132

Page **1** of **2**

Posted: **Tue Aug 09, 2005 7:44 am**

Could someone give me some tricky input.

Appreciate you. ^^

Appreciate you. ^^

Posted: **Tue Aug 09, 2005 8:07 am**

Are you handling square numbers properly.

Posted: **Tue Aug 09, 2005 2:10 pm**

Try the following input output set...

**Input:**
**Output:**
Hope it works.

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

Posted: **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:
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);
}
```

Posted: **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?

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?

Posted: **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
```

Posted: **Tue Aug 09, 2005 5:26 pm**

thanks for all, I got accept already.

I make an overflow on LCM computation.

thanks Shamim

I make an overflow on LCM computation.

thanks Shamim

Posted: **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...

Thanks jdmetz for pointing that. I have changed the output...

Posted: **Wed Aug 10, 2005 4:22 pm**

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

Posted: **Fri Aug 12, 2005 12:14 pm**

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

Posted: **Fri Aug 12, 2005 2:12 pm**

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

Posted: **Wed Aug 17, 2005 7:15 pm**

hi jdmetz,

can u please explain ur algorithm with prime solution?

can u please explain ur algorithm with prime solution?

Posted: **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);

}

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

{

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

}

Posted: **Sat Sep 24, 2005 10:37 pm**

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

Posted: **Thu Jun 29, 2006 2:42 pm**

it seems all right.but got WA.

Can anyone help?

Can anyone help?

Code: Select all

```
code deleted.
```