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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 5.00
AC-93
16 / 16 / 0
Регистрация: 27.01.2010
Сообщений: 150
#1

поиск количества делителей чисел от 1 до N - C++

08.02.2012, 07:10. Просмотров 1786. Ответов 5
Метки нет (Все метки)

итак задача
нужно посчитать кол-во чисел с одинаковым количество делителей, взять число перестановок, все перемножить, отнять единицу.
хранить кол-во чисел с кол-вом делителей можно в массиве (назовем его DEL) (кол-во делителей оценивается для больших N как корень третьей степени, т.е. тут максимум 2600 массив понадобится).
проблема как отыскать сколько у какого числа делителей.
пока придумал только такой вариант, читаем все входные, запоминаем порядок чисел, сортируем по возрастанию.
далее генерируем DEL , т.е. 2*10^9 слишком много, то можно использовать ползущий массив, который например по 100000 будет захватывать, а вычислять таким образом: берем каждое число по порядку (например i) и все n*i < верхней границы помечаем ++ делителей. т.е. взяли 5, пометили что там 1, потом 10 ++ , потом 15 и тд. когда достигаем числа из условий -считаем и выводим. Получается вроде как n*ln(n) сложность. Но прикинул- не проходит.
А какие еще варианты улучшения могут быть?

Добавлено через 7 минут
Просьба не писать код, т.к. все-таки контест длится и кто-то может обидеться, но указать куда копать.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.02.2012, 07:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос поиск количества делителей чисел от 1 до N (C++):

Задача на поиск делителей последовательности чисел с использованием функции - C++
Вводится последовательность целых чисел, 0 – конец последовательности. Для каждого числа последовательности найти количество его делителей...

Составить программу вычисления количества всех делителей всех чисел от 1 до n - C++
Дано натуральное число n.Составить программу вычисления количества всех делителей всех чисел от 1 до n

Поиск количества отрицательных чисел главной диагонали матрицы - C++
В матрице А6,6 найти произведение количества отрицательных чисел главной диагонали и количества положительных чисел 1-столбца. Суть...

Быстрое нахождение количества делителей натурального числа - C++
Как многие успели убедиться, часто требуется найти количество делителей натурального числа. Предлагаю быстрые алгоритмы для этой задачи. ...

Нахождение количества делителей числа через рекурсию - C++
Здравствуйте, я решал задачу на нахождение кол-ва делителей числа через рекурсию, вот код: void Rec(int x, int y, int Am) { if...

Функцией оформить определение количества делителей числа - C++
Вводится последовательность целых чисел, 0 – конец последовательности. Для каждого числа последовательности найти количество его делителей.

5
ejjjik
8 / 8 / 0
Регистрация: 06.06.2010
Сообщений: 25
08.02.2012, 17:00 #2
Цитата Сообщение от AC-93 Посмотреть сообщение
кол-во чисел с одинаковым количество делителей
поясните, просто например числа 2,3, 5 имеют два делителя, далее числа 4, 9 - имеют 3 делителя. какие числа суммировать?
1 2 3 4 5 6 7 8 9 10 // просто ряд
1 2 2 3 2 4 2 4 3 4 // кол-во делителей.
Цитата Сообщение от AC-93 Посмотреть сообщение
взять число перестановок
перестановок чего? ряда? или суммы этих делителей.


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
#include <iostream>
using std::cout;
using std::endl;
#include <windows.h> 
void sumDel( const int *arr, int size, int *del)
{
    for (int i = 0; i < size; i++ )
    {
        for (int j = 1; j <= arr[i]; j++ )
        {
            if ( (arr[i] % j) == 0) 
            {
                del[i]++;
            } 
        }
    }
}
 
const void print(int array[], int size)
{
    for (int i = 0; i <size; i++)
    {
        cout << array[i] << " ";
    }
}
 
int main()
{
    const int x = 30;
    int arrayOfNumber[x], arrayOfSumDel[x] = {0};
 
    for (int i = 0; i < x; i++ )
    {
        arrayOfNumber[i] = i + 1;
    }
 
    sumDel(arrayOfNumber, x, arrayOfSumDel);
 
    print(arrayOfNumber, x);
    cout << endl;
    print(arrayOfSumDel, x);
    cout << endl;
 
    Sleep(4000L);
    return 0;
}
0
AC-93
16 / 16 / 0
Регистрация: 27.01.2010
Сообщений: 150
08.02.2012, 17:14  [ТС] #3
В задаче нужно получить сколько вариантов, когда сейф может открыться, причем условие на возможность - кол-во делителей номера ячейки замка совпадает с кол-вом делителей лежащего в нем шарика.
у вас 3 числа по 2 делителя и 2 по 3, значит первые можно 3*2*1 способами расставить, вторые 2*1 способами, в итоге 3*2*1*2*1 - 1 (т.к. исключаем исходную комбинацию каждый в своем, ибо при этом сейф заперт из условия)


Что за код у вас написан?
0
ejjjik
8 / 8 / 0
Регистрация: 06.06.2010
Сообщений: 25
08.02.2012, 18:06 #4
количество делителей для каждого числа в последовательности от 1 до 30.
0
AC-93
16 / 16 / 0
Регистрация: 27.01.2010
Сообщений: 150
08.02.2012, 19:34  [ТС] #5
Ок, так не сработает, квадратичная сложность и памяти сам понимаешь.
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.02.2012, 20:33 #6
AC-93,
Если еще актуально, то обращайтесь в личку - есть одна идея (здесь описывать ее очень долго, и вопросов у Вас наверняка возникнет много, лучше все делать по ходу объяснений).
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.02.2012, 20:33
Привет! Вот еще темы с ответами:

Быстрый алгоритм для подсчета количества делителей числа - C++
Быстрый алгоритм для подсчета количества делителей натурального числа 1 &lt;= x &lt;= 1018. Помогите реализовать такой. Дело в том, что должно...

Определить кол-во чисел, имеющих ровно 5 делителей, среди 1-го миллиона натуральных чисел - C++
Среди первого миллиона десятичных натуральных чисел количество чисел, имеющих ровно пять делителей (единица и само число не учитываются),...

Определить количество чисел, имеющих ровно пять делителей, среди первого миллиона натуральных чисел - C++
Среди первого миллиона десятичных натуральных чисел количество чисел, имеющих ровно пять делителей (единица и само число не учитываются),...

Поиск делителей числа - C++
Доброго времени суток. Надо сделать кусок программы, в котором определяется, простое число или нет. При этом выполняться он должен за...


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

Или воспользуйтесь поиском по форуму:
6
Yandex
Объявления
09.02.2012, 20:33
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru