Форум программистов, компьютерный форум CyberForum.ru

МНОЖИТЕЛИ - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
18.11.2010, 16:30     МНОЖИТЕЛИ #1
Какое минимальное число можно представить как произведение 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)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2010, 16:30     МНОЖИТЕЛИ
Посмотрите здесь:

Определить простые множители C++
Множители C++
C++ Протые множители
Натуральное число на простые множители C++
Разложить на простые множители C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
24.11.2010, 17:13  [ТС]     МНОЖИТЕЛИ #21
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от #pragma Посмотреть сообщение
количество способов" != "количеству множителей"
количество способов равно количеству множителей/2 и в своем примере я ищу делители только до корня из н, тоесть ровно половину, а потом и сравниваю их
Цитата Сообщение от #pragma Посмотреть сообщение
"количеству простых делителей"
я ищу ВСЕ делители не только простые
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
27.11.2010, 23:03     МНОЖИТЕЛИ #22
"Я думал, думал, я всё понял!"(с)
Вот так 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
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.11.2010, 00:17     МНОЖИТЕЛИ #23
Mayonez, Вы ссылку на тестирующую систему можете дать, которая принимает эту задачу? Или ее не существует?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.12.2010, 12:39     МНОЖИТЕЛИ #24
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
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
04.12.2010, 18:45  [ТС]     МНОЖИТЕЛИ #25
valeriikozlov, за каким принципом работает программа?
сразу что-то не очень понятно
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.12.2010, 19:46     МНОЖИТЕЛИ #26
Цитата Сообщение от 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, Дальше продолжать?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2010, 19:55     МНОЖИТЕЛИ
Еще ссылки по теме:

C++ Множители
Разложить число на простые множители C++
C++ Разложить число на простые множители

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

Или воспользуйтесь поиском по форуму:
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
04.12.2010, 19:55  [ТС]     МНОЖИТЕЛИ #27
Цитата Сообщение от valeriikozlov Посмотреть сообщение
и мне не очень понятно

Цитата Сообщение от valeriikozlov Посмотреть сообщение
Mayonez, Дальше продолжать?
нет, спасибо большое за помощь
Yandex
Объявления
04.12.2010, 19:55     МНОЖИТЕЛИ
Ответ Создать тему
Опции темы

Текущее время: 12:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru