Какое минимальное число можно представить как произведение AxB ровно K способами?

@Mayonez · Регистрация: 26.12.2009

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

Какое минимальное число можно представить как произведение AxB ровно K способами.
AxB и ВxА считаются одним способом. К <= 50.
Пример:
вводится число К:
4
ответ:
24
1*24; 2*12; 3*8; 4*6; -----> 4 способа

Добавлено через 4 минуты

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int main()
{
   int n = 1; // с какого числа начинаем
   int kF;    //найденое количество делителей
   int k;
   cin >> k; //количество способов
   while (1)
   {
      int i;
      kF = 0;
      for (i = 1; (i*i) <= n; i++)
            if (n%i == 0) kF++;   //находим делители
      if (kF == k) {cout << n << endl; break;} //если количество
      // делителей совпадает с нужным - выходим из цикла
      n++; // иначе переходим к следующему числу
   }
   cout << n << endl;
   return 0;
}

вот такое написал я ...
но для чисел К =37, 46, 47, 31 - решение найти не удалось

@Mayonez · 24.11.2010, 17:13 **[ТС]**

Сообщение от #pragma

количество способов" != "количеству множителей"

количество способов равно количеству множителей/2 и в своем примере я ищу делители только до корня из н, тоесть ровно половину, а потом и сравниваю их

Сообщение от #pragma

"количеству простых делителей"

я ищу ВСЕ делители не только простые

@easybudda · 27.11.2010, 23:03

"Я думал, думал, я всё понял!"(с)
Вот так 50 уникальных делителей находит

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
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
int main(void){
    uint64_t c; /* искомое число */
    int k, i; /* количество уникальных делителей, счётчик циклов */
    uint64_t * div; /* массив делителей размером k + 1 */
    
    printf("k = ");
    if ( scanf("%d", &k) != 1 ){
        fprintf(stderr, "wrong input!\n");
        exit(1);
    }
    if ( k < 4 ){
        printf("too simple!\n");
        exit(1);
    }
    
    if ( ( div = (uint64_t*)malloc(sizeof(uint64_t) * (k + 1)) ) == NULL ){
        fprintf(stderr, "memory error!\n");
        exit(1);
    }
    
    div[0] = 1;
    div[1] = 2;
    div[2] = 3;
    for ( i = 3; i < (k + 1); ++i )
        div[i] = div[i-2] * 2;
    
    c = div[k] * div[k-1];
    for ( i = 0; i < k; ++i )
        printf("#%d:\t%llu X %llu = %llu\n", i + 1, div[i], c / div[i], c);
    
    free(div);
    exit(0);
}

мало того - до 64 досчитало...

для случая k < 4 сделать не сложно (намекну - при к = 3 с = 18)

Добавлено через 1 час 1 минуту
и снова облом - не самое маленькое число находится (спасибо, valeriikozlov)... Но прогресс на лицо, будем дальше думать...

valeriikozlov · 28.11.2010, 00:17

Mayonez, Вы ссылку на тестирующую систему можете дать, которая принимает эту задачу? Или ее не существует?

valeriikozlov · 02.12.2010, 12:39

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include "math.h"
#include "stdio.h"
#include <iostream>
using namespace std;
int mas_p[15], i_mas_p=0, mas[50][15], mas_temp[15], mas_temp_res[15];
bool pr(int a)
{
    if(a==2)
        return true;
    if(a%2==0)
        return false;
    for(int i=3; i<=(int)sqrt((double)a); i+=2)
        if(a%i==0)
            return false;
    return true;
}
 
void ras(int a)
{
    int i, j, y, fl=0;
    for(i=0; i<15; i++)
        if(mas_temp[i]%2==1)
            fl=1;
    if(fl==0) a++;
    fl=0;
    for(i=0; i<15; i++)
        mas_temp_res[i]=0;
    mas_temp_res[0]=1;
    for(i=0; i<15; i++)
    {
        for(j=0; j<mas_temp[i]; j++)
        {
            for(y=0; y<15; y++)
                mas_temp_res[y]*=mas_p[i];
            for(y=0; y<14; y++)
                if(mas_temp_res[y]>999)
                {
                    mas_temp_res[y+1]+=mas_temp_res[y]/1000;
                    mas_temp_res[y]%=1000;
                }
        }
    }
    for(i=14; fl==0 && i>=0; i--)
    {
        if(mas_temp_res[i]<mas[a-1][i])
            fl=1;
        if(mas_temp_res[i]>mas[a-1][i])
            fl=2;
    }
    if(fl==1)
    {
        for(i=0; i<15; i++)
            mas[a-1][i]=mas_temp_res[i];
    }
}       
 
 
void gen(int max, int tv, int i_p, int kv, bool fl)
{
    if(!fl)
    {
        mas_temp[1]++;
        gen(max, 2*tv+1, 1, tv, true);
        mas_temp[1]--;
    }
    else
    {
        if((tv+1)/2<=50)
            ras((tv+1)/2);
        if(tv+1<=50)
        {
            mas_temp[i_p+1]++;
            gen(max, 2*tv+1, i_p+1, tv, true);
            mas_temp[i_p+1]--;
        }
        if(mas_temp[i_p]<max && (tv+kv+1)/2<=50)
        {
            mas_temp[i_p]++;
            gen(max, tv+kv+1, i_p, kv, true);
            mas_temp[i_p]--;
        }
        else
            return;
    }
}
 
int main()
{
    int i, j;
    for(i=2; i<50; i++)
        if(pr(i))
            mas_p[i_mas_p++]=i;
    mas[0][0]=1;
    for(i=1; i<50; i++)
    {
        for(j=0; j<15; j++)
            mas[i][j]=mas[i-1][j]*4;
        for(int j=0; j<14; j++)
        if(mas[i][j]>999)
        {
            mas[i][j+1]+=mas[i][j]/1000;
            mas[i][j]%=1000;
        }
    }
    // 
    mas_temp[0]=0;
    for(i=1; i<98; i++)
    {
        mas_temp[0]++;
        gen(i, i, 0, i, false);
    }
    //
    for(i=0; i<50; i++)
    {
        bool fl=true;
        printf("K= %d  ", i+1);
        for(j=14; j>=0; j--)
        {
            if(!fl)
                printf("%03d", mas[i][j]);
            if(fl && mas[i][j]!=0)
            {
                fl=false;
                printf("%d", mas[i][j]);
            }
        }
        printf("\n");
    }
   return 0;
}

Mayonez, Проверил заодно и вашу программу. Считает она оказывается для К=46, только немного долго, но быстрее чем для К=43. Остальные значения: К =37, 47, 31 сами поймете почему не считала.

@Mayonez · 04.12.2010, 18:45 **[ТС]**

valeriikozlov, за каким принципом работает программа?
сразу что-то не очень понятно

valeriikozlov · 04.12.2010, 19:46

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

valeriikozlov, за каким принципом работает программа?
сразу что-то не очень понятно

Если честно, то и мне не очень понятно(шучу

)
Давайте сначало совсем без кода алгоритм объясню, потом понятней будет.
Здесь немного ДП и немного комбинаторики. Для начала заполняем массив mas[][] значениями степени 2 как написал в посте 11.
Далее рассматриваем числа произведения простых чисел. Смысл здесь такой, например К для числа 2*2*13*13 будет равно К для числа 2*2*3*3. Но число 2*2*3*3 заведомо меньше, чем число 2*2*13*13.
Вот по этому смыслу мы и перебираем все варианты наборов простых чисел, вычисляя их произведение (с использованием длинной арифметики), а также вычисляя число К для этого набора (и сравниваем с уже имеющимся числом для данного К).
Например есть набор простых чисел 2 2 2 3, то из этого набора родятся такие наборы чисел:
2 2 2 3 5
2 2 2 3 3

Добавлено через 13 минут
Mayonez, Дальше продолжать?

@Mayonez · 04.12.2010, 19:55 **[ТС]**

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

и мне не очень понятно

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

Mayonez, Дальше продолжать?

нет, спасибо большое за помощь

Новые блоги и статьи Все статьи Все блоги /
Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	28.11.2010, 00:17
	Mayonez, Вы ссылку на тестирующую систему можете дать, которая принимает эту задачу? Или ее не существует? 0

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874
	04.12.2010, 18:45 [ТС]
	valeriikozlov, за каким принципом работает программа? сразу что-то не очень понятно 0

Какое минимальное число можно представить как произведение AxB ровно K способами?

Решение