2

Для заданного целого положительного числа n найдите количество таких целых чисел x, лежащих в отрезке [1,n], что количество общих делителей у n и x равно заданному числу k. Например, если k=1, то требуется найти количество чисел, взаимнопростых c n, которые не превосходят его.

Входные данные В единственной строке входных данных через пробел заданы два целых положительных числа n и k (1≤n,k≤5000).

Выходные данные Выведите одно целое число — искомое количество.

Примеры

входные данные 2 1 выходные данные 1

входные данные 12 2 выходные данные 4

входные данные 13 1 выходные данные 12

входные данные 720 6 выходные данные 52

a = int(input())
b = int(input())
while a <= b:
        m = 0
        for i in range(1, a + 1):
            if a % i == 0:
                m += 1
        if m >= n:
            print(a, '-', m, end=' - ')
            for i in range(1, a + 1):
                if a % i == 0:
                    print(i, end=' ')
            print()
        a += 1

Вообще программа не идет, если не трудно напишите код, пожалуйста.

2 ответа 2

5

Эх, не знаю я Python... Может, кто переведет?

Не актуально - см. ниже :)

Немного теории.
Все общие делители двух чисел определяются разложением НОД этих чисел на простые сомножители. Если НОД G имеет разложение

введите сюда описание изображения

то количество общих делителей может быть записано как

введите сюда описание изображения

Число 5000 небольшое, так что факторизацию можно выполнять прямо по массиву простых чисел - их всего лишь 19, которые меньше квадратного корня из 5000.

По-моему, самый быстрый путь.

Код на C++:

#include <iostream>

using namespace std;
int gcd(int m, int n)  // Поиск наибольшего общего делителя
{
    while(m && n) if (m < n) n %= m; else m %= n;
    return m + n;
}

// Все возможные простые делители чисел до 5000
int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 };

// Проверка числа на k общих делителей
bool cnt(int n, int m, int k)
{
    int g = gcd(n,m);            // НОД
    int total = 1;               // Количество общих делителей

    // факторизуем НОД на простые сомножители; количество делителей -
    // произведение их степеней, увеличенных на 1
    for(int i = 0; g > 1 && i < size(primes); ++i)
    {
        int l = 0;
        while(g%primes[i] == 0) { g /= primes[i]; ++l; }
        total *= l+1;
    }
    return total == k;
}

int main(int argc, const char * argv[])
{
    int n, k, count = 0;
    cin >> n >> k;

    // Перебор всех чисел
    for(int m = 1; m < n; ++m)
        if (cnt(n,m,k)) count++;

    cout << count << endl;
}

Сравнение для 5000 2 с кодом @Psyperception по времени дает нефиксируемое :) время против 1.3 секунды...

С помощью напильника, Интернета и какой-то... перевел сам:

def gcd(m,n):
    while m>0 and n>0:
        if m < n : 
            n = n % m
        else:
            m = m % n
    return m + n;

primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]

def cnt(n,m,k):
    g = gcd(n,m)    
    total = 1

    for i in range(19):
        if g <= 1: break
        l = 0
        while g%primes[i] == 0:
            g = g // primes[i]
            l = l + 1
        total = total * (l+1)
    return total == k

n = int(input('n: '))
k = int(input('k: '))
count = 0
for m in range(1,n):
    if cnt(n,m,k) != 0: count = count + 1
print(count)

Должен заметить, что этот код на том же примере 5000 2, что у @Psyperception выполняется за 1.3 секунды, у меня выполняется за 0.02 секунды - так, всего в 65 раз быстрее :)

0

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

n = int(input('Введите число n: '))
k = int(input('Введите количество общих делителей k: '))
# эта функция возвращает количество всех общих 
делителей
def all_deliteli(a,b):
n = 0
for i in range(1, min(a, b) + 1):
    if a % i == b % i == 0:
        n += 1
return n
count_chisel = 0 # счетчик
""" Тут мы начинаем циклом проходить от 1 до указанного числа n.
    Проверяем общее число делителей двух чисел: 1 и 1, потом 
    1 и 2, 1 и 3 и т.д """
for x in range(1, n + 1):
    all_gcd = all_deliteli(x, n)
    if all_gcd == k: # Если число делителей совпадает с нашим 
указанным числом k, то мы увеличиваем счетчик
        count_chisel += 1 # вот тут
print(count_chisel)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.