I can not understand how this problem can be solved without the "stupid" sorting of numbers from the NOC / a given number, up to the NOC. The number to be found must be minimal to the data.

You can express the desired number through the GCD (unknown) * NOC / given_number, but then it is not clear how to go back from GCD to the number. You can also decompose the LCM and the melon number into prime factors, look for the third one by reference (the reference point is the product of the numbers that are in the LCM decomposition but not in the expansion of the number given to us), but there’s just a brute-force check (but a little smaller) . The second option is more difficult for very large numbers.

It is impossible to search through the numbers will be huge. I don’t ask you to write the code, the very essence of the decision is just interesting, whether I think at all.

  • In general, the problem has many solutions. For example, let the LCM = 84, and the number - 28. The second number may be 3, and 12, and 6, and 21 ... Well, of course, you can write out a number of possible solutions yourself, but you have a specific question. among ... - Harry
  • Yes, after - no sorting, although it seems that the second number cannot be decomposed into simple factors ... - Harry
  • So why not just divide the LCM by a known number? Immediately get one of the possible answers. - Yaant
  • @Yaant why not just divide the LCM into a known number? LCM = 4; x = 2. Share - you get 2. However, the correct (by the way, the only) answer is 4. - Akina
  • @Akina Yes, I’ve stepped on something, now I don’t understand how I argued when I decided that it was possible. :) - Yaant

3 answers 3

We decompose into prime factors of the NOC. We obtain a list of multiplier-multiplicity (for example, in the decomposition of 12 there will be two multipliers - 2 with multiplicity 2 and 3 with multiplicity 1). Let's call it a list1 . We decompose the available number into prime factors (let's call it a list2 ). Next, we process both lists, creating a list3 .

  • If a certain factor is absent from list1 , but is included in list2 , the task is unsolvable.

  • If the multiplicity of the multiplier in list1 is less than its multiplicity in list2 , the problem is unsolvable.

  • If a certain multiplier is in list1 , but not in list2 , it is placed in list3 with the same multiplicity as in list1 .

  • If the multiplicity of a multiplier in list1 is greater than its multiplicity in list2 , it is placed in list3 with the same multiplicity as in list1 .

  • If a certain multiplier exists in list1 and list2 with the same multiplicity, it is placed in list3 with a multiplicity of 0 (zero).

Multiplying the multipliers from list 3 taking into account the multiplicity, we obtain the minimum solution. The remaining solutions are obtained by increasing the multiplicity of one or several factors to the list3 , but not exceeding their multiplicity to the list1 .

Everything.

  • Thank you I couldn’t fully collect my thoughts, but you did it perfectly, thank you)) - Johanna
  • Improvement (tremendous acceleration of such an algorithm): divide the LCM (a, b) by a (suppose that a is given, b must be found) - this will be the initial b - and see what simple factors are in its decomposition. Then for each multiplier cycle: as long as we can divide a by a factor, the result (b) is multiplied by a factor. EVERYTHING. - Johanna
  • @Johanna look at the code in my answer (for the connection with the actions that you described). - jfs

If any solution is of interest, the NOC itself is the trivial (greatest) answer, since max(max(e, d), d) == max(e, d) , see canonical decomposition . If b and lcm(a, b) known, and you need to find any a , then the answer is: a = lcm(a, b) that is:

 lcm(a, b) == lcm(lcm(a, b), b)

In order to find the smallest possible solution, in prime factorization, the multiplicity of primes in the lowest common multiple (LCM) is equal to the maximum multiplicity of both numbers (see the canonical decomposition ), therefore the multiplicity in the desired (minimum among several possible solutions) or equal to LCM, or zero, if the multiplicity in the first number is equal to the multiplicity in the LCM:

 # a = p**d * ...; b = p**e * ...; lcm(a, b) = p**m ... where m = max(d, e) assert e <= m d = 0 if m == e else m

For small numbers, you can find prime factors by looking at all the divisors:

 def a(b, lcm): """Find *a* given *lcm(a, b)* and *b*.""" a = 1 p = 2 # prime factor while p * p <= b: # find multiplicity of p in b e = 0 # b = p**e * ... while b % p == 0: # found prime factor e += 1 # increase multiplicity b //= p assert lcm % p == 0 lcm //= p # find multiplicity of p in lcm # lcm = p**m * ... m = e while lcm % p == 0: # d = max(d, e) m += 1 # increase multiplicity lcm //= p # a = p**d * ... if m > e: # max(d, e) > e a *= p**m # d == m else: # d = 0 assert m == e p += 1 assert lcm % b == 0 # last prime factor or 1 if lcm % b**2 != 0: # e = max(d, e) lcm //= b return a * lcm 

 <script src="https://cdn.rawgit.com/brython-dev/brython/3.4.0/www/src/brython.js"></script><body onload="brython()"><script type="text/python"> def a(b, lcm): """Find *a* given *lcm(a, b)* and *b*.""" a = 1 p = 2 # prime factor while p * p <= b: # find multiplicity of p in b e = 0 # b = p**e * ... while b % p == 0: # found prime factor e += 1 # increase multiplicity b //= p assert lcm % p == 0 lcm //= p # find multiplicity of p in lcm # lcm = p**m * ... m = e while lcm % p == 0: # d = max(d, e) m += 1 # increase multiplicity lcm //= p # a = p**d * ... if m > e: # max(d, e) > e a *= p**m # d == m else: # d = 0 assert m == e p += 1 assert lcm % b == 0 # last prime factor or 1 if lcm % b**2 != 0: # e = max(d, e) lcm //= b return a * lcm def gcd(a, b): while b: a, b = b, a%b return a def lcm(a, b): return a * b // gcd(a, b) from browser import document @document["mybutton"].bind("click") def on_click(event): b = int(document["b"].value) lcm_ = int(document["lcm"].value) a_ = a(b, lcm_) assert lcm_ == lcm(a_, b) print(f"a={a_}, b={b}, lcm={lcm(a_,b)}") on_click('dummy on start') </script><label for="b">b:&nbsp;</label><input id="b" value="16"> <label for="lcm">lcm:&nbsp;</label><input id="lcm" value="80"> <button id="mybutton">Найти a</button></body>

Examples of using:

 >>> a(b=28, lcm=84) 3 >>> a(b=21, lcm=84) 4 >>> lcm(a(b=3, lcm=84), 3) 84 >>> a(b=2, lcm=4) 4 >>> a(b=4, lcm=4) 1 >>> a(b=20, lcm=80) 16 >>> a(b=16, lcm=80) 5 >>> a(b=1, lcm=lcm(2, 1)) 2 >>> a(b=2, lcm=lcm(2, 1)) 1 >>> lcm(a(b=2, lcm=lcm(2, 1)), 2) 2

where lcm(a, b) :

 from math import gcd def lcm(a, b): return a * b // gcd(a, b)

    Solution without explicit factorization. The complexity is not more than the number of prime divisors of the number (and on average much faster).

    Suppose we have the equality НОК = а*b/НОД(a,b) Or НОК/а = b/НОД(a,b) . We need to minimize b. The left part is given by the condition. It is clear that the minimum will be, with a minimum of GCD. Let it be 1. Then b1 = НОК/а . Any b will be divided by b1 (I think obviously) and can be written as b1 * c1 . Farther. c1 will be divided by gcd (a, b1). Continue iteratively until the process stops.

    The code is shorter than the explanation =)

     long calc(long nok, long first){ if (nok % first != 0) return -1; //wrong input long res = nok/first; long g = 1; long tmp; while ( (tmp = gcd(first, res)) != g){ g = tmp; res = nok/first * g; } return res; }

    A running test case https://ideone.com/HdBNgj