## 10892 - LCM Cardinality

Moderator: Board moderators

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Code: Select all

``````i=r*s/gcd(r,s);
``````
Both * and / have the same precedence and is left associative. That is, first multiplication is done, followed by division.

r*s suffers from overflow as its value can exceed MAX_INT_LIMIT..

2 solutions..
1] convert to r / gcd(r,s) * s or
2] use long long

sohag144
New poster
Posts: 14
Joined: Mon Feb 27, 2006 4:12 pm
Contact:
Thank you.I got accepted.

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Contact:

### 10892 - LCM Cardinality

I need some input and also some output for LCM Cardinality .

Problem no 10892.

A lot of thanks for Sender .

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Hi, I need some test cases, please...

Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
For prime input, my code gives output 2.
and..... what should be the output if the input is 1?

Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars
I have no scope here to compile my code in this time...
I think for input 1 output must be 1...
This is my algo ...
Compare Yourself...
1. 1st find all the divisor of the given input.Save in array and sort.
{
the way may recursive
or->
a loop i:from 2 to sqrt(N)
if(N%i == 0)
then add both i and N/i to the divisor list.
}
2. then use an N^2 loop to find whose lcm is the given. count them.

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

### I/0 for 10892

INPUT::
2
12
10000000
11111111
12345678
98746521
4587754
1
7485874
8888888
9999999
4512454
0

OUTPUT::
2 2
12 8
10000000 113
11111111 41
12345678 68
98746521 41
4587754 5
1 1
7485874 14
8888888 32
9999999 23
4512454 5

serendipity
New poster
Posts: 6
Joined: Tue May 09, 2006 9:22 pm
hey my code shows WA for perfect square number:( can someone tell me how to handle this problem?

wot is the prime algorithm for this cardinality problem?

--regards

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 10892 - LCM Cardinality

How can we solve the problem by prime factors method??

nasif2587
New poster
Posts: 2
Joined: Thu Jan 07, 2016 12:48 pm

### Re:

J&Jewel wrote:This problem can also be solved by the prime....solution...
hi J&Jewel, can you explain the prime factorization merhod for this problem?