Форум программистов, компьютерный форум 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
18.11.2010, 16:37     МНОЖИТЕЛИ #2
Может потому что таких чисел не существует или они слишком большие?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
18.11.2010, 16:40  [ТС]     МНОЖИТЕЛИ #3
Цитата Сообщение от Хохол Посмотреть сообщение
или они слишком большие?
в смысле 31!, 37!, 46!, 47! соответственно?
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
18.11.2010, 16:42     МНОЖИТЕЛИ #4
Нет, с чего бы. Просто очень большие. Или нет их вовсе.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.11.2010, 16:43     МНОЖИТЕЛИ #5
Mayonez, Все просто:
Если задано К, то что бы найти
минимальное число
, то нужно перемножить первые K-1 простые числа, это и будет ответ.
Нет, я свой ответ признаю ошибочным.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
18.11.2010, 16:45  [ТС]     МНОЖИТЕЛИ #6
да, спасибо нашёл! Ответ valeriikozlov верный тут почитать
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.11.2010, 16:51     МНОЖИТЕЛИ #7
Mayonez, Не совсем верный мой был ответ. Но в голове крутится...
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
18.11.2010, 22:40     МНОЖИТЕЛИ #8
Цитата Сообщение от Mayonez Посмотреть сообщение
в смысле 31!, 37!, 46!, 47! соответственно?
Абсолютно верно! Самое первое, что в голову приходит - факториал k. Гарантированно разделится на все числа от k до единицы. Но 50! слишком большое число...
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
18.11.2010, 22:55     МНОЖИТЕЛИ #9
easybudda, надо ровно k способами. С факториалами будет слишком много способов.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
19.11.2010, 01:05     МНОЖИТЕЛИ #10
вот так считает до 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
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
int test(uint64_t num, uint64_t div){
    if ( ! div )
        return 0;
    while ( div )
        if ( num % div-- )
            return 0;
    return 1;
}
 
void dump(uint64_t num, uint64_t div){
    uint64_t i;
    for ( i = 1; i <= div; ++i )
        printf("%llu * %llu = %llu\n", i, num / i, num);
}
 
#define TOP 1000000000LLU
 
int main(void){
    uint64_t num, k, m;
    
    printf("k = ");
    scanf("%llu", &k);
    
    for ( num = k * k, m = 0; m <= TOP; ++m ){
        if ( test(num + k * m, k) ){
            dump(num + k * m, k);
            break;
        }
    }
    
    if ( m > TOP )
        printf("Number too big!\n");
    
    return 0;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2010, 08:21     МНОЖИТЕЛИ #11
Цитата Сообщение от Хохол Посмотреть сообщение
Или нет их вовсе.
Такие числа точно существуют. Вот пример (я иду по степеням числа 2):
Число 2, К=1 (1*2)
Число 4, К=2 (1*4, 2*2)
Число 8, К=2 (1*8, 2*4)
Число 16, К=3 (1*16, 2*8, 4*4)
Число 32, К=3 (1*32, 2*16, 4*8)
Число 64, К=4 (1*64, 2*32, 4*16, 8*8)
Число 128, К=4 (1*128, 2*64, 4*32, 8*16)
Число 256, К=5 (1*256, 2*128, 4*64, 8*32, 16*16)
и т.д.
Получается что умножая на 4 любую степень 2, мы увеличиваем К на 1. Таким образом мы сможем получить и К =37, 46, 47, 31. Другой вопрос являются ли они минимальными? Но то что такие числа есть это точно.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
19.11.2010, 08:58     МНОЖИТЕЛИ #12
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Другой вопрос являются ли они минимальными?
не-а!
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Число 128, К=4 (1*128, 2*64, 4*32, 8*16)
При к = 4 минимальное число 24 было, немного меньше, чем 128
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2010, 09:05     МНОЖИТЕЛИ #13
easybudda, Я знаю, это был ответ посвященный только существованию таких чисел и не более.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
22.11.2010, 18:04  [ТС]     МНОЖИТЕЛИ #14
так всё-таки: решение существует но очень большое число или ...??
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 19:35     МНОЖИТЕЛИ #15
так всё-таки: решение существует но очень большое число или ...??
или решение тоже существует, но значение меньше. Если Вас все-таки интересует решение пишите в личку, подумаем вместе, я думаю решение найдем обязательно (потому что оно существует).
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
22.11.2010, 19:39     МНОЖИТЕЛИ #16
Цитата Сообщение от Mayonez Посмотреть сообщение
решение существует но очень большое число или ...?
Мало того, существует как минимум два решения! valeriikozlov, и я Вам их озвучили. Другое дело, что так не самые маленькие из возможных чисел получаются, но делящиеся без остатка на нужное количество делителей. Кстати, программа, которую я написал, тоже не самое меньшее из возможных чисел выдаёт...

Добавлено через 59 секунд
Цитата Сообщение от valeriikozlov Посмотреть сообщение
я думаю решение найдем обязательно
ага... я уже тетрадку целую в 18 листов исписал - пока фигня какая-то получается, но чувствую, что где-то рядом...
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 20:24     МНОЖИТЕЛИ #17
Мало того, существует как минимум два решения!
На самом деле решений для каждого К бесконечно... То что я привел для степеней 2, точно так же распостраняется для степеней любого простого числа.

Цитата Сообщение от easybudda Посмотреть сообщение
Кстати, программа, которую я написал, тоже не самое меньшее из возможных чисел выдаёт...
Я знаю.

На самом деле решение есть, а это самое главное. Осталось "пустяк" - найти его.
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
22.11.2010, 20:45     МНОЖИТЕЛИ #18
Я что-то не пойму, разве количество делителей равно количеству способов? Что-то не въеду никак.
Пример:
вводится число К:
4
ответ:
24
1*24; 2*12; 3*8; 4*6; -----> 4 способа
4 способа,а делителей сколько? 8? или тоже четыре? Я насчитал 8,вот и не пойму. Или имеется ввиду простые множители? Тогда их три: 1,2,3. Всех остальных участников этих умножений в примере можно получить с помощью простых.
Автор,поясните.
Или я что-то недопонял,как всегда,или у автора ошибка тут
C++
1
 if (kF/2 == k) {cout << n << endl; break;} //если количество
А на два делить нужно поскольку количество множителей всегда кратно двум согласно условию (участие одного и того же элемента в разных перестановках исключено)

И ещё один момент: Если i увеличиваем до корня числа,то как мы найдём множитель 24 в случае,когда n==24? (как раз в случае приведённого примера). Поэтому проверять нужно, наверное, до самого числа,и делать ещё один вложенный цикл,отметая повторения,или что-то в этом духе. Или я опять ошибся
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 20:50     МНОЖИТЕЛИ #19
#pragma, Из условия:
AxB и ВxА считаются одним способом.
Значит то что Вы насчитали 8 делителей это хорошо и правильно - поэтому К равно 4.

Добавлено через 1 минуту
Цитата Сообщение от #pragma Посмотреть сообщение
А на два делить нужно поскольку количество множителей всегда кратно двум согласно условию (участие одного и того же элемента в разных перестановках исключено)
Цитата Сообщение от Mayonez Посмотреть сообщение
Какое минимальное число можно представить как произведение AxB ровно K способами.
К может быть и нечетным числом
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.11.2010, 21:15     МНОЖИТЕЛИ
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
22.11.2010, 21:15     МНОЖИТЕЛИ #20
Цитата Сообщение от valeriikozlov Посмотреть сообщение
А на два делить нужно поскольку количество множителей всегда кратно двум согласно условию (участие одного и того же элемента в разных перестановках исключено)
Какое минимальное число можно представить как произведение AxB ровно K способами.
#pragma,
К может быть и нечетным числом
Не вижу противоречия между двумя Вами приведёнными предложениями,так как "количество способов" != "количеству множителей" а автор в своём коде сравнивает их напрямую.
Ладно, спорить не буду, может, я прогнал просто

Добавлено через 12 минут
поправка: "количество способов" != "количеству простых делителей" - вот их и сравнивает автор.
Yandex
Объявления
22.11.2010, 21:15     МНОЖИТЕЛИ
Ответ Создать тему
Опции темы

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