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

По количеству делителей числа определить само число - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.96
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
02.11.2011, 15:58     По количеству делителей числа определить само число #1
Название темы говорит само за себя, а теперь подробнее:

По заданному количеству делителей числа требуется найти само это число.
Входные данные

Во входном файле INPUT.TXT записано количество делителей D некоторого натурального числа N (1 <= D <= 5000).
Выходные данные

В выходной файл OUTPUT.TXT запишите число N. Если решений несколько, выведите наименьшее из них. Если решения нет, или наименьшее из решений превосходит 10^15+1, запишите в файл число 0.

Например:
3 -> 4
4 -> 6
12 -> 60
6 -> 5040
4911 -> 0.

Можете подсказать идею? Перебор не пойдет по времени, только если он хорошо оптимизированный.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2011, 15:58     По количеству делителей числа определить само число
Посмотрите здесь:

C++ Найти все трехзначные числа, такие, что сумма цифр равна А, а само число делиться на B
Число делителей числа N C++
C++ Проверить гипотезу: если сумма цифр числа делится на 3, то и само число делится на 3
Найти все трехзначные числа: "Само число и сумма цифр этого числа делятся на одно и то же число P" C++
C++ Определить количество четных делителей числа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.11.2011, 16:46     По количеству делителей числа определить само число #2
Dani, ссылку на задачу можете дать? (сначало хочу проверить свой вариант).
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
02.11.2011, 16:48  [ТС]     По количеству делителей числа определить само число #3
Конечно, вот - http://********/index.asp?main=task&id_task=289
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.11.2011, 16:56     По количеству делителей числа определить само число #4
я оказывается уже когда-то давно решал эту задачу. Тогда просто выложу код:
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
#if defined(_MSC_VER)
#define _CRT_SECURE_NO_DEPRECATE
#endif
 
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#if defined(__GNUC__)
 
#define __STDC_FORMAT_MACROS
#include <inttypes.h>
 
#elif defined(_MSC_VER)
 
typedef __int64 int64_t;
#define PRId64 "I64d"
#define SCNd64 "I64d"
 
#endif
int mas_prost[20]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};
int64_t N=-1;
int mas[20]={0};
int D, i_mas;
void fun_rec(int del, int pr, int64_t temp)
{
    if(temp<0 || temp>1000000000000001 || del>D)
        return;
    if(del==D)
    {
        if(N==-1)
        {
            N=temp;
            return;
        }
        else
        {
            if(N>temp)
                N=temp;
            return;
        }
    }
    mas[pr]++;
    int temp_del=mas[0], fl=1;
    for(int i=1; fl && i<20; i++)
    {
        if(mas[i])
            temp_del=temp_del*(mas[i]+1)+mas[i];
        else
            fl=0;
    }
    fun_rec(temp_del+1, pr, temp*mas_prost[pr]);
    mas[pr]--; mas[pr+1]++;
    if(pr<19)
    {
        int temp_del=mas[0], fl=1;
        for(int i=1; fl && i<20; i++)
        {
            if(mas[i])
                temp_del=temp_del*(mas[i]+1)+mas[i];
            else
                fl=0;
        }
        fun_rec(temp_del+1, pr+1, temp*mas_prost[pr+1]);
        mas[pr+1]--;
    }
}
 
int main()
{
   freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
   scanf("%d", &D);
   if(D==1)
       printf("1");
   else
   {
   if(D==2)
       printf("2");
   else
   {
       mas[0]=1;
       fun_rec(2, 0, 2);
       if(N==-1)
           printf("0");
       else
           printf( "%" PRId64, N);
   }
   }
    return 0;
}
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
02.11.2011, 17:42  [ТС]     По количеству делителей числа определить само число #5
спасибо, а можете еще идею описать в кратце?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 06:00     По количеству делителей числа определить само число #6
Цитата Сообщение от Dani Посмотреть сообщение
спасибо, а можете еще идую в кратце?
смогу, но только завтра... сейчас начинается банкет...

Добавлено через 12 часов 13 минут
Цитата Сообщение от Dani Посмотреть сообщение
спасибо, а можете еще идею описать в кратце?
Идея (то же самое, только раздельно и про себя хочу спросить сейчас, ):
Любое число (кроме 1) можно разложить на простые числа, например:
число 8
2 3 5 7 <- простые числа
3 0 0 0 <- количество простых чисел в разложении

число 6
2 3 5 7 <- простые числа
1 1 0 0 <- количество простых чисел в разложении

число 12
2 3 5 7 <- простые числа
2 1 0 0 <- количество простых чисел в разложении

Зная количество простых чисел в разложении, можно запросто узнать общее количество делителей числа:
изначально берем res=1 (любое число делится на 1), затем идем по нижней строке разложенного на множители числа в примерах сверху (количество простых чисел в разложении) и если значение не равно 0, то делаем так: res=res*mas[i] + mas[i];

Теперь еще такой факт:
К примеру количество делителей числа будет одинаково для таких чисел:
число 60
2 3 5 7 <- простые числа
2 1 1 0 <- количество простых чисел в разложении

число 150
2 3 5 7 <- простые числа
1 1 2 0 <- количество простых чисел в разложении
потому что сами наборы количества простых чисел в разложении у них "одинаковы"
но число 150 больше числа 60 . Т.е. если лексикографический порядок указанного набора больше, то и само число больше.

Теперь нам осталось узнать необходимый набор количества простых чисел в разложении, который обеспечивает нужное количество делителей числа. После этого, можно составить само число - делителю 2 самое большое значение, делителю 3, следующее, и т.д.

В моем коде используется рек функция, которая заполняет нижнюю строку разложенного на множители числа как в задаче "лесенки" с того же ******** - предыдущее значение mas[i-1] должно быть большим или равным mas[i], кроме того проверяется что найденное число меньше или равно 10^15+1 .
Что непонятно, спрашивайте.

Добавлено через 12 секунд
Цитата Сообщение от Dani Посмотреть сообщение
спасибо, а можете еще идею описать в кратце?
Идея (то же самое, только раздельно и про себя хочу спросить сейчас, ):
Любое число (кроме 1) можно разложить на простые числа, например:
число 8
2 3 5 7 <- простые числа
3 0 0 0 <- количество простых чисел в разложении

число 6
2 3 5 7 <- простые числа
1 1 0 0 <- количество простых чисел в разложении

число 12
2 3 5 7 <- простые числа
2 1 0 0 <- количество простых чисел в разложении

Зная количество простых чисел в разложении, можно запросто узнать общее количество делителей числа:
изначально берем res=1 (любое число делится на 1), затем идем по нижней строке разложенного на множители числа в примерах сверху (количество простых чисел в разложении) и если значение не равно 0, то делаем так: res=res*mas[i] + mas[i];

Теперь еще такой факт:
К примеру количество делителей числа будет одинаково для таких чисел:
число 60
2 3 5 7 <- простые числа
2 1 1 0 <- количество простых чисел в разложении

число 150
2 3 5 7 <- простые числа
1 1 2 0 <- количество простых чисел в разложении
потому что сами наборы количества простых чисел в разложении у них "одинаковы"
но число 150 больше числа 60 . Т.е. если лексикографический порядок указанного набора больше, то и само число больше.

Теперь нам осталось узнать необходимый набор количества простых чисел в разложении, который обеспечивает нужное количество делителей числа. После этого, можно составить само число - делителю 2 самое большое значение, делителю 3, следующее, и т.д.

В моем коде используется рек функция, которая заполняет нижнюю строку разложенного на множители числа как в задаче "лесенки" с того же ******** - предыдущее значение mas[i-1] должно быть большим или равным mas[i], кроме того проверяется что найденное число меньше или равно 10^15+1 .
Что непонятно, спрашивайте.
Yandex
Объявления
03.11.2011, 06:00     По количеству делителей числа определить само число
Ответ Создать тему
Опции темы

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