Считаем пары если заданы НОД и НОК

Question

Код не проходит по времени. Задано два натуральных числа A и B. Найти кол-во таких пар чисел (P, Q), для которых A является НОД(P, Q), а B - НОК(P, Q).

Входные данные :

В единственном ряде два натуральных числа A и B (A < 10^5, B ≤ 10^6).

Исходящие:

Искомое количество таких пар.

Пример:

Входные данные : 3 60

Исходящие: 4

Мне кажется, нужно как-то удачнее range подобрать чтобы программа ускорилась. Сколько не пробовал, ничего не выходит. Или может есть какой-то более быстрой метод нахождения НОД и НОК?

Ссылка на задание (на украинском языке)

Вот мой код :

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

def lcm(a, b):
    m = a * b
    while a != 0 and b != 0:
        if a > b:
            a %= b
        else:
            b %= a
    return m // (a + b)
a, b = [int(el) for el in input().split()]
counter = 0
for i in range(a, b+1):
    for k in range(a, b+1):
        if a == gcd(i, k) and b == lcm(i, k):
            counter += 1
print(counter)

Answer 1

Попробуйте так:

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

a, b = [int(el) for el in input().split()]
counter = 0
for i in range(a, b+1):
    for k in range(a, b+1):
        tmp_gcd = gcd(i, k)
        if a == tmp_gcd and b == i * k / tmp_gcd:
            counter += 1
print(counter)

улучшаем:

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

a, b = [int(el) for el in input().split()]
counter = 0
for i in range(a, b+1):
    for k in range(i, b+1):
        tmp_gcd = gcd(i, k)
        if a == tmp_gcd and b == i * k / tmp_gcd:
            counter += 1
print(counter * 2)

следующий вариант:

from fractions import gcd

a, b = [int(el) for el in input().split()]
counter = 0
for i in range(a, b+1):
    for k in range(i, b+1):
        tmp_gcd = gcd(i, k)
        if a == tmp_gcd and b == i * k // tmp_gcd:
            counter += 1
print(counter * 2)

Answer 2

Можно испробовать такой путь - разложение НОК на простые множители содержит все множители искомых чисел. А разложение НОД - общие множители.

Таким образом - отделяем из множителей НОК ту часть, которая участвует в НОД, и смотрим, сколькими способами можно оставшиеся (а для нахождения оставшихся сами НОД и НОК факторизовать не нужно, только их отношение) разделить на две части. Сдаётся мне, что результат будет степенью двойки...

Пример подсчёта простых множителей:

 def factors(k):
    cnt = 0
    d = 2
    plus = 1
    while d * d <= k:
        while (k % d == 0):
            k //= d
            cnt += 1
        d += plus
        if d == 3:
            plus = 2
    if k > 1:
        cnt += 1
    return cnt

Answer 3

Перебирать пары p, q - тупиковое решение. Оптимальный перебор для (1, 10^6) потребует 499999500000 (10^6*(10^6 - 1) / 2) итераций. Решать нужно по другому, без непосредственной проверки пар.

Вот решение. Пояснения ниже.

def n_of_prime_divisors(n):
    c = 0
    d = 2
    while d * d <= n:
        if n % d == 0:
            while n % d == 0:
                n //= d
            c += 1
        d += 1
    if n > 1:
        c += 1
    return c


a, b = map(int, input().split())
if b % a != 0:
    print(0)
else:
    print(2 ** n_of_prime_divisors(b // a))

Если b не делится на a, то решений нет совсем. НОК всегда делится на НОД. Далее будем считать что b делится на a.

Пусть пара (p, q) решает задачу для (a, b), то есть a = НОД(p, q), b = НОК(p, q).

Тогда пара (p/a, q/a) решает задачу для (1, b/a), то есть 1 = НОД(p/a, q/a), b/a = НОК(p/a, q/a).

Следовательно количество пар для задач (a, b) и (1, a/b) одинаково. Далее будем решать задачу (1, n).

Задача сведена к поиску взаимнопростых пар (p, q), таких что p * q = n. Другими словами: сколькими способами n можно разложить в произведение двух взаимнопростых множителей.

Разложим n на простые: n = s1^e1 * s2^e2 * ... * sk^ek где si - различные простые, ei - натуральные.

Для примера рассмотрим s1. Он должен попасть в p или в q или в оба, так как их произведение равно n, а в n он есть. Если s1 входит и в p и в q, то p и q не взаимно простые. Следовательно, s1^e1 или входит целиком в p или целиком в q.

Сколькими способами можно распределить множители si^ei между p и q? Таких способов 2^k (k - количество различных простых делителей n). Доказывается по индукции по k.

Задача сведена к подсчёту различных простых делителей числа. В программе выше это делается элементарными средствами, так как нам нужно проверить только sqrt(n) кандидатов в делители. n <= 10^6 - всего тысяча итераций в худшем случае.

В процедуре явно не проверяется что делители простые, это не нужно. Составной делитель не может попасть в счёт, так как его простые множители уже исключены из n ранее.

Пример:

$ echo 3 60 | python gcd-lcm.py 
4

$ echo 1 510510 | python gcd-lcm.py 
128

Answer 4

рискну ускорить ответ мистера @Stanislav Volodarskiy...

def factors(n):    # (cf. https://stackoverflow.com/a/15703327/849891)
    # изменено под пайтон3, Внимание! возвращает генератор!
    j = 2
    while n > 1:
        for i in range(j, int((n+0.05) ** 0.5) + 1):
            if n % i == 0:
                n //= i
                j = i
                yield i
                break
        else:
            if n > 1:
                yield n
                break

a, b = map(int, input().split())
if b % a != 0:
    print(0)
else:
    print(2 ** len(set([x for x in factors(b // a)])))

БЛОГ НА HUSL

Считаем пары если заданы НОД и НОК

Ответы (4 шт):