Well, since the most important issue is knowing if the elements of the first set being primes or not to the second set, you can simply calculate the least common multiple, without caring about this, because if x,y are relative primes, than lcm(x,y) = x*y
On 3 April 2012 09:05, vivek dhiman <[email protected]> wrote: > let us assume.. a,b,c are relative primes to each other > and d,e,f are also relative primes to each other. > > what happens in that case ? > > > On Tue, Apr 3, 2012 at 5:23 PM, Renato Parente <[email protected]>wrote: > >> (Sorry for the quite long e-mail) >> >> You can try to think about Venn's Diagram >> http://en.wikipedia.org/wiki/Venn_diagram >> In a nutshell, for this case, realize 6 circles, >> one that includes all numbers divided by 'a', >> other that includes all numbers divided by 'b', >> and so on, ending with the circle that includes >> all numbers divided by 'f'. Now, visualize you >> can have intersection between these circles, >> these ones inform you which elements are >> divisible by both of these circles, e.g. the >> intersection of the first and the second circles >> informs us which numbers are divided by both >> 'a' and 'b'. Let's assume, for simplicity, that all >> of these numbers are relative prime. >> >> Let's see now the subset corresponding to the >> intersection of the first, second and fourth >> circles. They'll inform us which numbers are >> divided by 'a', 'b' and 'd', simultaneously. >> Notice this subset is also included at the >> intersection of ('a', 'b'), of ('a', 'd') and ('b', 'd') >> subsets. Since they've been counted three times >> and we only need one, we naturally subtract >> two time the number of elements in the subset >> ('a', 'b', 'd'). >> >> In the end (I swear this'll look painful, but it'll >> make some sense), let's see now the subset >> corresponding to the 'a', 'b', 'd' and 'e' circles. >> Naturally they'll inform which numbers are >> divided by all of these 4 numbers. Notice that >> the ('a', 'b', 'd', 'e') subset will appear in other >> subsets, such as ('a', 'b', 'd'), ('a', 'b', 'e'), >> ('a', 'd', 'e') and ('b', 'd', 'e') subsets, which have >> been subtracted (from previous steps). >> You'll need to notice that you had subtracted it >> 4 times, 3 of those which have been >> unnecessary subtractions, so you'll need to add >> them back again, multiplied by three. You'll do >> that again for subsets which include 5 circles and 6. >> >> This is called Inclusion-Exclusion principle, it's >> more explained online (a start up: >> http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle ). >> Well, for this problem, since you want all numbers less than k which >> represent this is the same thing as wanting all numbers less or equal >> to (k-1), and it's quite easy to know how many elements are in the >> subset of each, for instance, of subset ('a', 'b'), the number of >> elements inside of it is (k-1)/(a*b). >> For this problem there are only two more issues to be >> pointed out. First, it's natural that there aren't relative primes in >> these sets. To solve that out, instead of the simple product of numbers, >> you'll need to find the least common multiple of the numbers of each >> subset (it's pretty easy to code this). Second, when you apply this >> principle, realize if I have numbers of a single 'partition' >> (either numbers only from ('a', 'b', 'c') or ('d', 'e', 'f')), I do not >> need to >> consider them at all, simply ignore it and go for the next step. >> >> Having any doubts, please don't hesitate of asking or >> looking at other sites :) >> >> On 3 April 2012 05:18, vivek dhiman <[email protected]> wrote: >> >>> Than you Igor. >>> But can you explain the last addition.. >>> >>> >>> >>> On Tue, Apr 3, 2012 at 12:09 AM, Igor Naverniouk <[email protected]>wrote: >>> >>>> Inclusion-Exclusion principle. >>>> >>>> Add all the numbers that are divisible by >>>> - a and d >>>> - a and e >>>> - a and f >>>> - b and d >>>> - ... >>>> - c and f >>>> >>>> Subtract all the numbers that are divisible by >>>> - a, b and d >>>> - a, c and d >>>> - b, c and d >>>> - ... >>>> - c, e and f >>>> >>>> Add back all the numbers that are divisible by >>>> - a, b, c and d >>>> - ... >>>> - c, d, e and f. >>>> >>>> ... >>>> >>>> igor >>>> >>>> On 2 April 2012 11:36, vivek dhiman <[email protected]> wrote: >>>> >>>>> Hi all smart people. >>>>> >>>>> if there are two set of numbers (both sets are of size 3) >>>>> (a,b,c) and (d,e,f) >>>>> >>>>> given a number k, how will you count all numbers(n) < k that are >>>>> divisible by both x and y >>>>> where x is any number from set (a,b,c) >>>>> and y is any number from set (d,e,f) >>>>> >>>>> remember you should take care of repetitions.. >>>>> >>>>> Thing is I am doing this using sets and iterators which is taking much >>>>> more time ..suggest some better approach .. >>>>> No need to write code... just the approach.. >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Google Code Jam" group. >>>>> To post to this group, send email to [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/google-code?hl=en. >>>>> >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Google Code Jam" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/google-code?hl=en. >>>> >>> >>> >>> >>> -- >>> Regards >>> Vivek Dhiman >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Google Code Jam" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/google-code?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. >> > > > > -- > Regards > Vivek Dhiman > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
