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

Найти все совершенные числа от M до N - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
02.08.2014, 21:01     Найти все совершенные числа от M до N #1
Совершенные числа
(Время: 1 сек. Память: 16 Мб )
Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Требуется найти все совершенные числа от M до N.

Входные данные

Входной файл INPUT.TXT содержит числа M и N, разделенные пробелом. (1 <= M <= N <= 5*1018)

Выходные данные

В выходной файл OUTPUT.TXT выведите по одному числу в строке в порядке возрастания все совершенные числа, находящихся на отрезке [M, N]. В том случае, когда таких чисел нет следует вывести «Absent».

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
#include <stdio.h>
#include <math.h>
 
int main()
{
    int mas[8]={2, 3, 5, 7, 13, 17, 19, 31};
    long M, N, temp;
    int fl=1, i, fl1=0;
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%ld%ld", &M, &N);
    for(i=0; i<8 && fl; i++)
    {
        temp=long(pow((double)2,(double) mas[i]-1)*(pow((double)2,(double)mas[i])-1));
        if(temp>=M && temp<=N)
        {
            printf("%ld\n", temp);
            fl1=1;
        }
        if(temp>N)
            fl=0;
    }
    if(!fl1){printf("Absent");}
  return 0;
}
Пролетает на 10 тесте, подскажите, где ошибка? Заранее благодарен
http://********/index.asp?main=task&id_task=364
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
02.08.2014, 21:11     Найти все совершенные числа от M до N #2
Я понять не могу, в чём удовольствие решать задачи из какого-то сайта, если решения для них ты копипастишь с форума на другом сайте? Я понимаю, когда школота тут свою домашку спрашивает... Но ведь участие в конкурсах - дело добровольное!
_Ivana
2189 / 1394 / 124
Регистрация: 01.03.2013
Сообщений: 4,151
Записей в блоге: 2
02.08.2014, 21:29     Найти все совершенные числа от M до N #3
Kuzia domovenok, имхо это хороший вариант освоить язык и методы. Я тоже порой увлекаюсь задачами с сайтов, и если у меня что-то не получается - задаю вопросы на форумах и набираюсь уму-разуму от специалистов.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
02.08.2014, 22:28     Найти все совершенные числа от M до N #4
Neoks, 5 * 1018 это 5 * 10^18?
щас загуглил и в википедии там даны эти совершенные числа, короче берешь пихаешь их в массив и отправляешь)
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 06:50  [ТС]     Найти все совершенные числа от M до N #5
Kuzia domovenok, решал задачи по нарастающей сложности, а эту решить не смог, лучше узнать решение
у более умных людей, чем не решить вовсе

Добавлено через 22 секунды
SlavaSSU, не интересно же
CyberSolver
 Аватар для CyberSolver
101 / 74 / 17
Регистрация: 23.07.2014
Сообщений: 686
Записей в блоге: 1
03.08.2014, 07:35     Найти все совершенные числа от M до N #6
Цитата Сообщение от Neoks Посмотреть сообщение
SlavaSSU, не интересно же
Зато правильно. Есть такой класс задач. Ну либо вспомнить про простые числа Мерсенна. Если вы ещё знаете специальные алгоритмы для них (проверки на простоту) - тогда точно в секунду уложитесь.
Mr.X
Эксперт С++
 Аватар для Mr.X
2803 / 1579 / 247
Регистрация: 03.05.2010
Сообщений: 3,669
03.08.2014, 09:34     Найти все совершенные числа от M до N #7
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
131
132
133
134
/////////////////////////////////////////////////////////////////////////////////////////
//СОВЕРШЕННЫЕ ЧИСЛА
//(Время: 1 сек. Память: 16 Мб )
//Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. 
//Требуется найти все совершенные числа от M до N.
//ВХОДНЫЕ ДАННЫЕ
//
//Входной файл INPUT.TXT содержит числа M и N, разделенные пробелом. (1 <= M <= N <= 5*10^18)
//
//ВЫХОДНЫЕ ДАННЫЕ
//
//В выходной файл OUTPUT.TXT выведите по одному числу в строке в порядке возрастания все 
//совершенные числа, находящихся на отрезке [M, N]. В том случае, когда таких чисел нет 
//следует вывести «Absent».
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
typedef long long       T_int;
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::set<T_int>    T_int_set;
/////////////////////////////////////////////////////////////////////////////////////////
void    print_perfect_numbers_from_to
        (
            T_int   min,
            T_int   max
        )
{
    T_int_set  perfect_numbers;
 
    perfect_numbers.insert( 6                   );
    perfect_numbers.insert( 28                  );
    perfect_numbers.insert( 496                 );
 
    perfect_numbers.insert( 8128                );
    perfect_numbers.insert( 33550336            );
    perfect_numbers.insert( 8589869056          );
 
    perfect_numbers.insert( 137438691328        );
    perfect_numbers.insert( 2305843008139952128 );
 
    auto    min_val_it  =   perfect_numbers.lower_bound( min );
    auto    max_val_it  =   perfect_numbers.upper_bound( max );
 
    if  (
            min_val_it  ==  max_val_it
        )
    {
        std::cout   <<  "Absent"
                    <<  std::endl;
    }
    else
    {
        std::copy
            (
                min_val_it,
                max_val_it,
                std::ostream_iterator<T_int>( std::cout, "\n" )
            );
    }//else
}
/////////////////////////////////////////////////////////////////////////////////////////
void    print_prompt_and_input_val_in_segment
            (
                T_str   const   &   prompt,
                double          &   val,
                T_int               left_bound,
                T_int               right_bound
            )
{
    do
    {
        std::cout   <<  prompt;
        std::cin    >>  val;
    }
    while   (
                    val             <   left_bound
                ||  right_bound     <   val
            );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_int     const   MIN_BOUND_VAL   =   1;
    T_int     const   MAX_BOUND_VAL   =   T_int (
                                                    5 * pow( 10.0,  18.0 )
                                                );
 
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl;
 
        std::cout   <<  "Введите границы отрезка ("
                    <<  MIN_BOUND_VAL
                    <<  ".."
                    <<  MAX_BOUND_VAL
                    <<  "):"
                    <<  std::endl;
 
        double     min =   0;
 
        print_prompt_and_input_val_in_segment
            (
                "min = ",
                min,
                MIN_BOUND_VAL,
                MAX_BOUND_VAL
            );
 
        double     max =   0;
 
        print_prompt_and_input_val_in_segment
            (
                "max = ",
                max,
                T_int( min ),
                MAX_BOUND_VAL
            );
 
        print_perfect_numbers_from_to
            (
                T_int( min ),
                T_int( max )
            );
    }//for
}
Бендерродригез
Сгибальщик
 Аватар для Бендерродригез
42 / 42 / 3
Регистрация: 18.05.2013
Сообщений: 220
Завершенные тесты: 1
03.08.2014, 10:17     Найти все совершенные числа от M до N #8
Цитата Сообщение от Neoks Посмотреть сообщение
не интересно же
А зачем по-твоему на собеседованиях задают задачи про 2 шнура и про круглые люки канализации спрашивают?
Надо ли городить код, если можно просто использовать данные из открытого доступа?
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
03.08.2014, 10:29     Найти все совершенные числа от M до N #9
Цитата Сообщение от Бендерродригез Посмотреть сообщение
Надо ли городить код, если можно просто использовать данные из открытого доступа?
Надо. Если бы это была какая-то олимпиада и полагался бы какой-то приз, то там все методы хороши. А тут задачи чисто для общего развития. А если изменить чуть-чуть условия? Методы решения будут те же, а в инете ответа не найдётся.
Бендерродригез
Сгибальщик
 Аватар для Бендерродригез
42 / 42 / 3
Регистрация: 18.05.2013
Сообщений: 220
Завершенные тесты: 1
03.08.2014, 11:35     Найти все совершенные числа от M до N #10
Цитата Сообщение от Somebody Посмотреть сообщение
Надо. Если бы это была какая-то олимпиада и полагался бы какой-то приз, то там все методы хороши. А тут задачи чисто для общего развития. А если изменить чуть-чуть условия? Методы решения будут те же, а в инете ответа не найдётся.
Недавно как раз читал об излишнем желании повторного использования кода. К чему писать "универсальный" метод, если есть более простое решение под данное условие?
Вот поменяются условия чуть-чуть, тогда и решай задачу по-другому, с классами и парсерами.
Умение не делать лишнего (которое в будущем подарит радостные часы поиска багов) - это так же общее развитие.
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,656
Записей в блоге: 1
03.08.2014, 11:50     Найти все совершенные числа от M до N #11
Ясно дело, 5*1018 не влезает в long и надо использовать long long
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 12:01  [ТС]     Найти все совершенные числа от M до N #12
Бендерродригез, даже если так, то не проходит по времени
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
03.08.2014, 12:35     Найти все совершенные числа от M до N #13
Neoks, кинь готовый код, я просто не понимаю, как она может не проходить по времени!
И кстати, то что эти числа высиляются по такой формуле, ты же тоже загуглил xD.
Твой код с лонг лонгами работает у меня.
Jewbacabra
1791 / 1506 / 540
Регистрация: 24.04.2014
Сообщений: 4,236
03.08.2014, 12:38     Найти все совершенные числа от M до N #14
Neoks, Быстрый поиск совершенных чисел
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 13:52  [ТС]     Найти все совершенные числа от M до N #15
SlavaSSU,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <fstream>
using namespace std;
int main ()
{
int c[8]={6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128};
int a,b;
cin>>a>>b;
for(int i=0;i<=7;i++)
    for(int j=a;j<=b;j++)
if (j==c[i])
    cout<<c[i]<<endl;
else
    cout<<"absent";
return 0;
}
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
03.08.2014, 13:59     Найти все совершенные числа от M до N #16
Neoks, ох как. как она вообще до 10 теста доходила.

надо так

C++ (Qt)
1
2
3
for(int i = 0; i < 8; i++)
if(c[i] >= a && c[i] <= b)
cout << c[i] << ' ';
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 14:22  [ТС]     Найти все совершенные числа от M до N #17
SlavaSSU, пожалуйста, напишите программу полностью, я не понял
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
03.08.2014, 14:30     Найти все совершенные числа от M до N #18
Neoks,
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <fstream>
 
using namespace std;
 
int main ()
{
    long long c[8]={6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128};
    long long a, b;
    cin >> a >> b;
    bool ok = false;
    for(int i = 0; i < 8; i++)
    {
        if(c[i] >= a && c[i] <= b)
        {
            cout << c[i] << ' ';
            ok = true;
        }
    }
 
    if(!ok)
        cout << "Absent" << endl;
    return 0;
}
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,051
03.08.2014, 14:42     Найти все совершенные числа от M до N #19
Цитата Сообщение от SlavaSSU Посмотреть сообщение
for(int i = 0; i < 8; i++)
{
if(c[i] >= a && c[i] <= b)
{
cout << c[i] << ' ';
ok = true;
}
}
так ради прикола
другое решение
C++
1
2
3
4
5
6
7
int i=0;
for( ;i<8 && c[i]<a;i++);
for(;i<8 && c[i]<=b;i++)
 {
   cout << c[i] << ' ';
   ok = true;
 }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.08.2014, 15:25     Найти все совершенные числа от M до N
Еще ссылки по теме:

Найти все совершенные числа меньшие заданного C++
C++ Найти все совершенные числа, меньшие заданного
В двумерном массиве найти совершенные числа C++

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

Или воспользуйтесь поиском по форуму:
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 15:25  [ТС]     Найти все совершенные числа от M до N #20
SlavaSSU, не проходит по времени
Yandex
Объявления
03.08.2014, 15:25     Найти все совершенные числа от M до N
Ответ Создать тему
Опции темы

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