10892 - LCM Cardinality

[sohel]

a part of your code.

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]

Thank you.I got accepted.

[Mushfiqur Rahman]

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

Problem no 10892.

A lot of thanks for Sender .

[nymo]

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

[Tanu]

Think about the prime input...

[nymo]

For prime input, my code gives output 2.
and..... what should be the output if the input is 1?

[Tanu]

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]

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]

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]

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

[nasif2587]

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

hi J&Jewel, can you explain the prime factorization merhod for this problem?