Найти количество делителей двух чисел

@dmitrii2000 · Регистрация: 03.05.2020

Студворк — интернет-сервис помощи студентам

Дано натуральное число n. Подсчитайте количество таких пар чисел (a;b), что:

a и b — делители n;
a<b;
a и b — взаимно простые;
ab≤n.
Входные данные

Вводится натуральное число n≤108.

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

Выведите количество таких пар.

Примеры
Ввод
10
Вывод
4

@mat_bub · 19.07.2021, 11:09

Здравствуйте, Catstail, ваше решение почти правильное, я его лишь доработал под данное условие.

Во-первых, ab≤n, а не ab<n.

Во-вторых, условие задачи не очень правильное по моему мнению. 1 считается за простое число, хотя это не так. Таким образом получаем 4 пары чисел: (1, 10);(1, 5);(1, 5);(2, 5).

Учитывая эти факторы, выкладываю доработанное решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int gcd(int a, int b)
{
    int tmp;
    while(b != 0)
    {
        tmp=a%b;
        a=b;
        b=tmp;
    }
    return a;
}
 
int main()
{
    vector<int> factors;
    int n,k,sz,a,b,c;
    cin >> n;
    
    k=1;
    while (k*k<=n)
    {
        if (n%k==0)
        {
            factors.push_back(k);
            if (n/k != k) factors.push_back(n/k);
        }
        k++;
    }
    
    sort(begin(factors), std::end(factors));
 
    sz=factors.size();
    c=0;
    
    for (int i=0; i<sz-1; i++)
        for (int j=i+1; j<sz; j++)
        {
            a=factors[i];
            b=factors[j];
            if ((gcd(a,b)==1) && (a*b<=n)) 
            {
                c++;
            }
        }    
    
    cout << c;
 
    return 0;
}

P.s. Первый раз пишу на данном форуме, если что-то не так, извините.

@grizlik78 · 19.07.2021, 12:47

Сообщение от mat_bub

Во-вторых, условие задачи не очень правильное по моему мнению. 1 считается за простое число, хотя это не так.

А в задании ничего и нет про простые числа. Там про взаимно простые, а 1 действительно считается взаимно простым с любым числом.

@Iltner A · 06.07.2024, 22:36

1. разложим число n на простые множители.
получится разложение вида:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\small \mathit{\mathbf{n = {{p}_{1}}^{{a}_{1}}\cdot {{p}_{2}}^{{a}_{2}}\cdot...\cdot{ {p}_{s}}^{{a}_{s}}}}$

2. Пользуясь комбинаторикой я вывел формулу для ответа:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\small \mathit{\mathbf{ans\:=\: \frac{(2{a}_{1}\: +\: 1)\cdot (2{a}_{2}\: +\: 1)\cdot\: ...\: \cdot (2{a}_{s}\: +\: 1)\: -\: 1}{2}}}$

т.е. остаётся только перебрать все простые делители и посчитать ответ.
мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using ll = long long;
 
int main() {
    ll n;
    cin >> n;
    set<ll> dels;
    map<ll, ll> cntd;
    ll f = 2;
    while(f * f <= n){
        if(n % f == 0){
            n /= f;
            dels.insert(f);
            cntd[f]++;
        }
        else f++;
    }
    if(n - 1) {
        dels.insert(n);
        cntd[n]++;
    }
    ll fi = 1;
    for(auto d : dels){
        fi *= (2 * cntd[d] + 1);
    }
    fi = (fi - 1)/ 2;
    cout << fi;
}

@TheCalligrapher · 07.07.2024, 06:34

Сообщение от Iltner A

Пользуясь комбинаторикой я вывел формулу для ответа:

Формула для ответа - (a₁+1)(a₂+1)...(a_s+1) - здесь уже не раз приводилась (Поиск подходящих чисел). Формула фактически очевидным образом вытекает из факторизации числа. Поэтому как и зачем вы умудрились запихать в свой вариант эти странные умножения и деления на 2 - не ясно.

Более того, по вашей формуле получается, что число 20 (= 2²*5¹) имеет 7 делителей (=((2*2+1)(2*1+1)-1)/2). Но правильный ответ - 6 (=(2+1)(1+1)).

@grizlik78 · 07.07.2024, 10:01

Сообщение от TheCalligrapher

Более того, по вашей формуле получается, что число 20 (= 22*51) имеет 7 делителей (=((2*2+1)(2*1+1)-1)/2). Но правильный ответ - 6 (=(2+1)(1+1)).

Возможно вы решаете разные задачи. Для числа 20 число делителей действительно 6 (1, 2, 4, 5, 10, 20), но количество пар, удовлетворяющих условиям исходной задачи на самом деле 7: (1, 2), (1, 4), (1, 5), (1, 10), (1, 20), (2, 5), (4, 5).

@TheCalligrapher · 07.07.2024, 18:09

Сообщение от grizlik78

Возможно вы решаете разные задачи.

Да, вы правы. Я почему-то не понял, что формула Iltner A - ответ для исходной задачи, а не просто для количества делителей.

@TheCalligrapher · 24.08.2024, 01:23

Для начала уберем требование a<b из условия задачи. Пусть нас интересует P(x) - количество таких пар (a, b) для числа x, в котором (a, b) и (b, a) считаются разными парами. Обратите внимание, что теперь пара (1, 1) тоже учитывается и это единственная "симметричная" пара.

1. Взглянем на искомую функцию P(x).

Пусть y и z - взаимно просты (эквивалентно: простые факторизации y и z не содержат одинаковых факторов).

Пусть взаимно простая пара (a, b) входит в P(y), а взаимно простая пара (c, d) входит в P(z). Очевидно, что ac|yz (делит) и bd|yz.
Ясно также, что числа ac и bd - взаимно просты. Действительно, если, скажем, c и b имеют общий простой фактор, то это противоречит взаимной простоте y и z.
То есть пара (ac, bd) будет входить в P(yz).

В другую сторону, пусть пара (e, f) входит в P(yz). Факторизация e будет содержать только простые факторы чисел y и z. Обозначим произведение первых через a, а вторых - через c, т.е. e=ac. Аналогичным образом разложим f в произведение f=bd. Мы получим пары (a, b) и (c, d). Понятно, что и a, и b делит y. При этом общих простых факторов у a и b нет (в противном случае e и f не были бы взаимно простыми), что значит, что a и b - взаимно простые. То есть (a, b) входит в P(y). Аналогичным образом: (c, d) входит в P(z).

Несложно видеть, что таким образом мы получили взаимно однозначное соответствие между каждой комбинацией пар (a, b) из P(y) и (с, d) из P(z) и парой (ac, bd) из P(yz). Из этого следует мультипликативность функции P(x), то есть для взаимно простых y и z выполняется P(yz) = P(y)P(z)

2. Пусть x=pⁿ, где p - простое число. Чему равно P(x)? Очевидно, что это будет пара (1, 1) и всевозможные пары вида (1, p^k) и (p^k, 1) для k=1..n. Общее количество таких пар равно 2n+1.

3. Так как функция P(x) мультипликативна, для любого числа x, факторизация которого имеет вид p^kq^lr^m..., функция P(x) будет равна (2k+1)(2l+1)(2m+1)...

4. А теперь вернем требование a<b в условие задачи. Тут же из общего набора допустимых пар исчезнет пара (1, 1), а из остального набора допустимых пар исчезнут пары-нарушители, которых будет ровно половина.

Это и даст нам искомую формулу: для числа x=p^kq^lr^m... ответ задачи равен ((2k+1)(2l+1)(2m+1)... - 1)/2

P.S. На шаге 3 видно, что P(x) равна количеству делителей x².

@TheCalligrapher · 24.08.2024, 19:59

P.P.S. Интересно было бы найти какой-то более-менее несложный способ взаимно однозначного отображения между такими парами для x и делителями x². Это привело бы к более "конструктивному" (и потому более наглядному) выводу формулы из пункта 3. Навскидку у меня не получилось найти такое отображение.

@Runer543221 · 26.08.2024, 22:00

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <numeric>
 
unsigned gcd(unsigned a, unsigned b)
{
  if (!a || !b) return a + b;
  while (a != b) if (a > b) a -= b; else b -= a;
  return a; 
}
 
int main() {
    long long n;
    std::cin >> n;
 
    std::vector<long long> divisors;
    for (long long i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) {
                divisors.push_back(n / i);
            }
        }
    }
 
    int count = 0;
 
    for (size_t i = 0; i < divisors.size(); ++i) {
        for (size_t j = i + 1; j < divisors.size(); ++j) {
            long long a = divisors[i];
            long long b = divisors[j];
 
            if (a < b && gcd(a, b) == 1 && a * b <= n) {
                count++;
            }
        }
    }
 
    std::cout << count << std::endl;
 
    return 0;
}

@TheCalligrapher · 26.08.2024, 22:35

Правильное решение уже приводилось в аналогичной теме: Найти количество делителей двух чисел

@Royal_X · 26.08.2024, 23:18

Сообщение от Runer543221

C++
1
#include <numeric>

ну раз подключаешь это, то зачем всё это

Сообщение от Runer543221

C++
1
2
3
4
5
6
unsigned gcd(unsigned a, unsigned b)
{
if (!a || !b) return a + b;
while (a != b) if (a > b) a -= b; else b -= a;
return a;
}

просто используй std::gcd из <numeric>

тем более, у тебя один из самых медленных алгоритмов для вычисления gcd на основе вычитаний. Можно же использовать алгоритм на основе %.

Хотя, в код не вникал и, возможно, там всё нужно менять...

Новые блоги и статьи Все статьи Все блоги /
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202

	Найти количество делителей двух чисел 09.07.2021, 08:08. Показов 11778. Ответов 30 Метки нет (Все метки) Дано натуральное число n. Подсчитайте количество таких пар чисел (a;b), что: a и b — делители n; a<b; a и b — взаимно простые; ab≤n. Входные данные Вводится натуральное число n≤108. Выходные данные Выведите количество таких пар. Примеры Ввод 10 Вывод 4 0

@TheCalligrapher Вездепух 13215 / 6847 / 1826 Регистрация: 18.10.2014 Сообщений: 17,345
	24.08.2024, 01:23
	Для начала уберем требование a<b из условия задачи. Пусть нас интересует P(x) - количество таких пар (a, b) для числа x, в котором (a, b) и (b, a) считаются разными парами. Обратите внимание, что теперь пара (1, 1) тоже учитывается и это единственная "симметричная" пара. 1. Взглянем на искомую функцию P(x). Пусть y и z - взаимно просты (эквивалентно: простые факторизации y и z не содержат одинаковых факторов). Пусть взаимно простая пара (a, b) входит в P(y), а взаимно простая пара (c, d) входит в P(z). Очевидно, что ac\|yz (делит) и bd\|yz. Ясно также, что числа ac и bd - взаимно просты. Действительно, если, скажем, c и b имеют общий простой фактор, то это противоречит взаимной простоте y и z. То есть пара (ac, bd) будет входить в P(yz). В другую сторону, пусть пара (e, f) входит в P(yz). Факторизация e будет содержать только простые факторы чисел y и z. Обозначим произведение первых через a, а вторых - через c, т.е. e=ac. Аналогичным образом разложим f в произведение f=bd. Мы получим пары (a, b) и (c, d). Понятно, что и a, и b делит y. При этом общих простых факторов у a и b нет (в противном случае e и f не были бы взаимно простыми), что значит, что a и b - взаимно простые. То есть (a, b) входит в P(y). Аналогичным образом: (c, d) входит в P(z). Несложно видеть, что таким образом мы получили взаимно однозначное соответствие между каждой комбинацией пар (a, b) из P(y) и (с, d) из P(z) и парой (ac, bd) из P(yz). Из этого следует мультипликативность функции P(x), то есть для взаимно простых y и z выполняется P(yz) = P(y)P(z) 2. Пусть x=pⁿ, где p - простое число. Чему равно P(x)? Очевидно, что это будет пара (1, 1) и всевозможные пары вида (1, p^k) и (p^k, 1) для k=1..n. Общее количество таких пар равно 2n+1. 3. Так как функция P(x) мультипликативна, для любого числа x, факторизация которого имеет вид p^kq^lr^m..., функция P(x) будет равна (2k+1)(2l+1)(2m+1)... 4. А теперь вернем требование a<b в условие задачи. Тут же из общего набора допустимых пар исчезнет пара (1, 1), а из остального набора допустимых пар исчезнут пары-нарушители, которых будет ровно половина. Это и даст нам искомую формулу: для числа x=p^kq^lr^m... ответ задачи равен ((2k+1)(2l+1)(2m+1)... - 1)/2 P.S. На шаге 3 видно, что P(x) равна количеству делителей x². 1

@TheCalligrapher Вездепух 13215 / 6847 / 1826 Регистрация: 18.10.2014 Сообщений: 17,345
	24.08.2024, 19:59
	P.P.S. Интересно было бы найти какой-то более-менее несложный способ взаимно однозначного отображения между такими парами для x и делителями x². Это привело бы к более "конструктивному" (и потому более наглядному) выводу формулы из пункта 3. Навскидку у меня не получилось найти такое отображение. 0

@TheCalligrapher Вездепух 13215 / 6847 / 1826 Регистрация: 18.10.2014 Сообщений: 17,345
	26.08.2024, 22:35
	Правильное решение уже приводилось в аналогичной теме: Найти количество делителей двух чисел 0

Найти количество делителей двух чисел

Решение