10892 - LCM Cardinality

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by sohel » Thu Jun 29, 2006 3:29 pm

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
New poster
Posts: 14
Joined: Mon Feb 27, 2006 4:12 pm
Location: Dhaka,Bangladesh
Contact:

Post by sohag144 » Thu Jun 29, 2006 6:26 pm

Thank you.I got accepted.

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

10892 - LCM Cardinality

Post by Mushfiqur Rahman » Wed Jul 05, 2006 12:02 pm

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

SOME TESTCASES PLEASE...

Post by nymo » Thu Jul 13, 2006 6:01 pm

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

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

Post by Tanu » Tue Jul 18, 2006 12:24 pm

Think about the prime input...

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

Post by nymo » Wed Jul 19, 2006 6:42 am

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

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

Post by Tanu » Wed Jul 19, 2006 8:25 am

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

Post by murkho » Sat Jul 22, 2006 4:38 pm

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

Post by serendipity » Tue Sep 12, 2006 10:55 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

Post by richatibrewal » Thu Nov 13, 2014 6:16 pm

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

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

Re:

Post by nasif2587 » Wed Feb 17, 2016 6:42 pm

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?

Post Reply

Return to “Volume 108 (10800-10899)”