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

@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 на основе вычитаний. Можно же использовать алгоритм на основе %.

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

Новые блоги и статьи Все статьи Все блоги /
мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .

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

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

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

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

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

Решение