#include <stdio.h>
#include <math.h>
int main(int argc, char* argv[])
{
const long long limit=100000I64*100000I64*100000I64+1I64;
double min,v;
long long res=1I64;
int D,nums[12]={2,3,5,7,11,13,17,19,23,29,31,37},
divisors[12],temp[12],count=0,index;
bool stop;
scanf("%d",&D);
index=sqrt((double)D);
for (int i=2;i<=index;)
if (D%i==0)
{
D/=i;
temp[count]=i-1;
count++;
}
else
i++;
if (D>1)
{
temp[count]=D-1;
count++;
}
for (int i=0;i<count;i++)
divisors[count-1-i]=temp;
for (int i=count-1;i>=1;i--)
{
min=30000.0;
for (int j=i-1;j>=0;j--)
{
v=(double)(divisors[j]+1)*log((double)nums[j]);
if (v<min)
{
min=v;
index=j;
}
}
if (min<log((double)nums))
{
divisors[index]=(divisors[index]+1)*(divisors+1)-1;
divisors=0;
}
}
stop=false;
for (int i=0;i<count&&!stop;i++)
for (int j=0;j<divisors&&!stop;j++)
{
res*=(long long)nums;
stop=res>limit;
}
if (stop)
printf("0");
else
printf("%I64d",res);
getchar();
getchar();
return 0;
}
[C++]Найти число по заданному количеству делителей
По заданному количеству делителей числа требуется найти само это число.
Входные данные
Во входном файле INPUT.TXT записано количество делителей D некоторого числа N (1 <= D <= 5000).
Выходные данные
В выходной файл OUTPUT.TXT запишите число N. Если решений несколько, выведите наименьшее из них. Если решения нет, или наименьшее из решений превосходит 1015+1, запишите в файл число 0.
Входные данные
Во входном файле INPUT.TXT записано количество делителей D некоторого числа N (1 <= D <= 5000).
Выходные данные
В выходной файл OUTPUT.TXT запишите число N. Если решений несколько, выведите наименьшее из них. Если решения нет, или наименьшее из решений превосходит 1015+1, запишите в файл число 0.
Я так понимаю, что рассматриваются только натуральные числа. В случае если делители - любые целые, то решение всегда 1. Если же делители должны являться простыми числами, то наименьшим решением будет 2 в степени количества делителей.
1015+1 - это не много, так что можно перебрать все числа и у каждого найти число делителей.
На сколько я понимаю - все делители должны быть разными. В таком случае наименьшим решение будет D!, а если 1 не считать делителем, то (D+1)!
там не 1015+1 а 10^15+1
ещё примеры входных и выходних данных
№ INPUT.TXT OUTPUT.TXT
1_______3______________ 4
2_______4_______________6
3_______12____________ 60
4_______60____________ 5040
5_______4911____________ 0
ещё примеры входных и выходних данных
№ INPUT.TXT OUTPUT.TXT
1_______3______________ 4
2_______4_______________6
3_______12____________ 60
4_______60____________ 5040
5_______4911____________ 0
Цитата: specter
На сколько я понимаю - все делители должны быть разными. В таком случае наименьшим решение будет D!, а если 1 не считать делителем, то (D+1)!
Это не правда. у D! делителей значительно больше.
например в случае 1*2*3*4 = 24 6 - тоже делитель.
Цитата: H!RURG
там не 1015+1 а 10^15+1
ещё примеры входных и выходних данных
№ INPUT.TXT OUTPUT.TXT
1_______3______________ 4
2_______4_______________6
3_______12____________ 60
4_______60____________ 5040
5_______4911____________ 0
ещё примеры входных и выходних данных
№ INPUT.TXT OUTPUT.TXT
1_______3______________ 4
2_______4_______________6
3_______12____________ 60
4_______60____________ 5040
5_______4911____________ 0
Это меняет дело. Я не знаю как такое решать.
Плохая задачка.
Только перебор, возможно, немного оптимизированный, больше ничего я в инете не нашёл, даже на сайте про последовательности, вот тут универсальной формулы для этой последовательности (миннимальное число с заданным количеством делителей) нет.
Только перебор, возможно, немного оптимизированный, больше ничего я в инете не нашёл, даже на сайте про последовательности, вот тут универсальной формулы для этой последовательности (миннимальное число с заданным количеством делителей) нет.
Цитата: Somebody
Плохая задачка.
Только перебор, возможно, немного оптимизированный, больше ничего я в инете не нашёл, даже на сайте про последовательности, вот тут универсальной формулы для этой последовательности (миннимальное число с заданным количеством делителей) нет.
Только перебор, возможно, немного оптимизированный, больше ничего я в инете не нашёл, даже на сайте про последовательности, вот тут универсальной формулы для этой последовательности (миннимальное число с заданным количеством делителей) нет.
Немного опоздал с ответом, но вот моё решение:
1) Количество простых делителей 12 (2^12=4096, 2^13=8192). Будем работать с разложением числа. Тогда выписываем первые 12 простых чисел.
2) D раскладываем на простые множители и сопоставляем их каждому простому числу в порядке убывания (84=2*2*3*7 => 2:6, 3:2, 5:1, 7:1).
3) Получаем число 2^6*3^2*5^1*7^1. Проходим по степеням с конца массива. Если число уменьшится при переносе степени на более раннюю позицию, то выполнится условие: a^u*b^v>a^((u+1)*(v+1)-1) (a<b).
Получаем: lnb>(u+1)lna. Если это условие выполняется, то при переносе число уменьшится. Для максимального уменьшения выбираем минимум чисел (u+1)lna. Для числа a ставим степень (u+1)*(v+1)-1, для числа b - 0.
4) Проходим по массиву и находим произведение чисел a^u. Если число превышает 10^15+1, то останавливаемся.
Общая сложность алгоритма O(sqrt(D)). Можно оптимизировать шаг 3), но и так скорость высокая, поэтому не стОит. И никакого перебора не нужно.
Код:
Цитата: Carbon
Немного опоздал с ответом, но вот моё решение:
1) Количество простых делителей 12 (2^12=4096, 2^13=8192). Будем работать с разложением числа. Тогда выписываем первые 12 простых чисел.
2) D раскладываем на простые множители и сопоставляем их каждому простому числу в порядке убывания (84=2*2*3*7 => 2:6, 3:2, 5:1, 7:1).
3) Получаем число 2^6*3^2*5^1*7^1. Проходим по степеням с конца массива. Если число уменьшится при переносе степени на более раннюю позицию, то выполнится условие: a^u*b^v>a^((u+1)*(v+1)-1) (a<b).
Получаем: lnb>(u+1)lna. Если это условие выполняется, то при переносе число уменьшится. Для максимального уменьшения выбираем минимум чисел (u+1)lna. Для числа a ставим степень (u+1)*(v+1)-1, для числа b - 0.
4) Проходим по массиву и находим произведение чисел a^u. Если число превышает 10^15+1, то останавливаемся.
Общая сложность алгоритма O(sqrt(D)). Можно оптимизировать шаг 3), но и так скорость высокая, поэтому не стОит. И никакого перебора не нужно.
1) Количество простых делителей 12 (2^12=4096, 2^13=8192). Будем работать с разложением числа. Тогда выписываем первые 12 простых чисел.
2) D раскладываем на простые множители и сопоставляем их каждому простому числу в порядке убывания (84=2*2*3*7 => 2:6, 3:2, 5:1, 7:1).
3) Получаем число 2^6*3^2*5^1*7^1. Проходим по степеням с конца массива. Если число уменьшится при переносе степени на более раннюю позицию, то выполнится условие: a^u*b^v>a^((u+1)*(v+1)-1) (a<b).
Получаем: lnb>(u+1)lna. Если это условие выполняется, то при переносе число уменьшится. Для максимального уменьшения выбираем минимум чисел (u+1)lna. Для числа a ставим степень (u+1)*(v+1)-1, для числа b - 0.
4) Проходим по массиву и находим произведение чисел a^u. Если число превышает 10^15+1, то останавливаемся.
Общая сложность алгоритма O(sqrt(D)). Можно оптимизировать шаг 3), но и так скорость высокая, поэтому не стОит. И никакого перебора не нужно.
не понял алгоритм:
число 12 - это рассматривается частный случай?
А откуда тогда берётся D?
Откуда берётся 84?
Цитата: P*t*
не понял алгоритм:
число 12 - это рассматривается частный случай?
А откуда тогда берётся D?
Откуда берётся 84?
число 12 - это рассматривается частный случай?
А откуда тогда берётся D?
Откуда берётся 84?
12 - это максимальное число делителей для данной задачи, т.к. D<=5000.
84 - пример для числа D.
ЗЫ Кстати, при D=84 ответ 20160.;)
Вроде алгоритм ясен но код не работает
Цитата: H!RURG
Вроде алгоритм ясен но код не работает
У меня работает, а не в консольном ли C++ тестится?
Нет тестится не в консольном а с помошю файлов но просто мой компилятор Dev C++ выдал некторые ошибочки
Цитата: H!RURG
Нет тестится не в консольном а с помошю файлов но просто мой компилятор Dev C++ выдал некторые ошибочки
Какие ошибки?
6:37 C:\Documents and Settings\Администратор\Рабочий стол\test.cpp invalid suffix "I64" on integer constant
я убрал IN64 теперь компилируется но ответ равен 0 всегда
я убрал IN64 теперь компилируется но ответ равен 0 всегда
Цитата: H!RURG
6:37 C:\Documents and Settings\Администратор\Рабочий стол\test.cpp invalid suffix "I64" on integer constant
я убрал IN64 теперь компилируется но ответ равен 0 всегда
я убрал IN64 теперь компилируется но ответ равен 0 всегда
Это из-за константы limit.
Код:
const long long limit=(long long)100000*(long long)100000*(long long)100000+(long long)1;
Всё супер тестится токо на 23 тесте ошибочка выходит если хочешь зайди проверь http://acm.dvpion.ru/index.asp?main=bstatus&id_t=289