Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
 Аватар для Mayonez
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874

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

18.11.2010, 16:30. Показов 3640. Ответов 26
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Какое минимальное число можно представить как произведение 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 - решение найти не удалось
1
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
18.11.2010, 16:30
Ответы с готовыми решениями:

Сколькими способами можно представить число N как сумму K чисел?
Здравствуйте, я решаю одну задачку из тимуса. Попробовал решить ее полным перебором, но даже после сильной оптимизации все равно не...

А какое минимальное число слагаемых потребуется, чтобы представить число 9002 в таком виде?
Число 2020 можно представить в виде суммы четырех различных чисел, каждое из которых записывается хотя бы двумя цифрами и все цифры в них...

Сколькими способами можно представить число
Сколькими способами можно представить число 12 в виде а) 4 неотрицательных целых слагаемых б)4 положительных целых слагаемых, если...

26
 Аватар для Mayonez
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
24.11.2010, 17:13  [ТС]
Лучший ответ Сообщение было отмечено как решение

Решение

Студворк — интернет-сервис помощи студентам
Цитата Сообщение от #pragma Посмотреть сообщение
количество способов" != "количеству множителей"
количество способов равно количеству множителей/2 и в своем примере я ищу делители только до корня из н, тоесть ровно половину, а потом и сравниваю их
Цитата Сообщение от #pragma Посмотреть сообщение
"количеству простых делителей"
я ищу ВСЕ делители не только простые
2
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12848 / 7597 / 1766
Регистрация: 25.07.2009
Сообщений: 13,985
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)... Но прогресс на лицо, будем дальше думать...
1
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
28.11.2010, 00:17
Mayonez, Вы ссылку на тестирующую систему можете дать, которая принимает эту задачу? Или ее не существует?
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
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 сами поймете почему не считала.
1
 Аватар для Mayonez
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
04.12.2010, 18:45  [ТС]
valeriikozlov, за каким принципом работает программа?
сразу что-то не очень понятно
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
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, Дальше продолжать?
1
 Аватар для Mayonez
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
04.12.2010, 19:55  [ТС]
Цитата Сообщение от valeriikozlov Посмотреть сообщение
и мне не очень понятно

Цитата Сообщение от valeriikozlov Посмотреть сообщение
Mayonez, Дальше продолжать?
нет, спасибо большое за помощь
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
04.12.2010, 19:55

Сколькими способами можно представить число 10 в виде 5
Сколькими способами можно представить число 10 в виде 5 а) неотрицательных б) положительных целых слагаемых, если представления,...

Сколькими способами число 11^n можно представить в виде трёх сомножителей
1.Сколькими способами число 11^n можно представить в виде трёх сомножителей (Представления, отличающиеся порядком сомножителей, считаются...

Сколькими способами можно представить число 13 в виде суммы 4 слагаемых?
Сколькими способами можно представить число 13 в виде суммы 4 слагаемых? а) числа различные, больше 0 или 0 б) числа различные, больше...

Найти натуральное число n, которое можно представить двумя разными способами
Привет! Нужно найти натуральное число n, которое можно представить двумя разными способами в виде суммы кубов двух натуральных чисел.

Определить за какое минимальное число шагов можно получить заданное число используя указанные операции
Сломанный калькулятор может делать только две операции: прибавлять к числу единицу и возводить число в квадрат. Изначально на дисплее...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
27
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru