Делители

[plan]

Как найти число(минимальное) по заданному к-ву делителей?
Например для 3 - 4,для 4 – 6, для 6 -12, для 5-16 и т. д.
З.Ы. перебор желательно не использовать(если перебор, то быстрый)

[GrAnd]

Во первых ты не получишь однозначного решения. Так как, например чисел с 3 делителями много (4, 9 и т.п. в основном все квадраты и прочие степени чисел). Аналогично и с другими числами.  

[HOMO_PROGRAMMATIS]

2GrAnd:
Человек русским языком просит МИНИМАЛЬНОЕ число

[HOMO_PROGRAMMATIS]

Не думайте что я тут выпендрился и забыл, я усиленно размышляю над задачей... Блин, все мозги уже свернул а к ответу почти и не приблизился Ессно, я ищу математическое решение без всякого перебора.

[plan]

Вот-вот, математическое мне как раз нужно... ???

[HOMO_PROGRAMMATIS]

Надеюсь мозги мои выдержат и я решу. Ждите... Но на меня сильно не надейтесь, у меня ещё куча всякой гадости вроде задания по матану.

Сообщение отредактировано: HOMO_PROGRAMMATIS - 05.03.03, 13:55

[albom]

Эта задача была на областной Владимирской олимпиаде по информатике среди школьников сего года.
Я эту задачу не решил, то есть решил, но использовал перебор (в этой задаче "быстрого" перебора не существует).
Поэтому решать можно только математикой....

---

Для начала сделаем два замечания. Во-первых, пусть некоторое число М разложено на простые множители, т.е. М = Пp_i^di.Тогда число различных его делителей, включая 1 и М, можно вычислить по формуле П_(di+1). Для решения поставленной задачи необходимо, чтобы это выражение было равно N. Во-вторых, если с учетом первого замечания подобрать такие d_i, чтобы М было минимальным, то решением данной задачи будет М = 2^d13^d25^d37^d411^d5…
После этих двух замечаний легко видеть, что данная задачи решается следующим образом: сначала необходимо перебрать все разбиения числа N на множители (их при заданных ограничениях будет не больше 9), затем для каждого разбиения определить d_i, и по ним вычислить М, и, наконец, выбрать среди полученных М минимальное.

---

PS. N - число делителей, M - искомое число.

Сообщение отредактировано: albom - 05.03.03, 20:08

[plan]

To albom:
Слушай, нафига разбивать N на множители ??? Ведь не обязательно у N и M будут общие делители  :) и только не говори мне, что из твоей формулы M=..... при различных d1,d2,d3 всегда будет M с кол-вом делителей, равным N.(если ты хочешь определять d1,d2,d3 ,то перебор будет ещё больше) ; хотя может я чего-то недопонял?....

P.S. У нас тоже эта задача на областной была. "Шоу" называлась. Я решил перебором, но, по-моему, перебор не решение...(у тебя нет решения с олимпиады? )...

[plan]

Всё-всё, допёрло до пенька(т.е. до меня)! Если кто парится из-зи меня, то Вы уж простите.

To albom:
     N:=(d1+1)*(d2+1)*(d3+1)…(di+1);
     И если N так разложить, то из твоей формулы М всегда будет иметь ровно N делителей;
     теперь как сделать, чтобы М было минимальным: во-первых, d1>=d2;d2>=d3…;
     во-вторых, i (т.е. кол-во множителей 2*3*5*7*11…) зависит от di, например:
     2^3=8(N=4,N=(3+1)*(0+1)… ),или 2^1 * 3^1 =6(N=4,N=(1+1)*(1+1)*(1+0))

Хотя, можно можно получить все М и выбрать минимальное…
     

[albom]

Рассмотрим алгоритм на примере, когда N=24.
Итак, раскладываем число N на простые множители: 24=2*2*2*3.
Так как всего множителей только 4, то берем первые 4 простых числа: 2, 3, 5, 7. Теперь нам нужно подобрать нужные показатели степеней к этим числам, причем показатели степени должны быть такими, что если прибавить к каждой к ним по единице, а потом перемножить их, то произведение будет равно 24.
Теперь можно начинать перебор (на самом деле здесь не много вариантов).
Возьмем такие степени 23, 0, 0, 0 (действительно (23+1)*(0+1)*(0+1)*(0+1)=24), тогда мы получаем число 2²³+3⁰+5⁰+7⁰=8388608. Хм, большое число, но у него ровно 24 делителя. В этом этапе мы решили, что 24=24*1*1*1.
Теперь у нас есть такой вариант, что 24=8*3*1*1. Тогда мы получаем степени (8-1), (3-1), 0, 0.
Подставляем их, получаем: 2⁷+3²+5⁰+7⁰=1152. Получили меньшее число, запомним его.
Теперь пора сделать маленькое замечание, т.к. простые числа идут у нас в порядке возрастания, то показатели степеней должны не возрастать. Т.е. случай, когда 24=3*8 (и показатели степеней равны 2, 7, 0, 0) не рассматривается.
Теперь подумаем, как еще можно разложить число 24 на множители? Ага, можно попробовать так: 24=12*2*1*1. Тогда показатели степеней равны 11, 1, 0, 0. И мы получаем число  2¹¹+3¹+5⁰+7⁰=6144 - явно не лучший вариант.
Далее по аналогии:
24=6*4*1*1, степени 5, 3, 0, 0, число: 2⁵+3³+5⁰+7⁰=864.
24=6*2*2*1, степени 5, 1, 1, 0, число: 2⁵+3¹+5¹+7⁰=525.  
24=4*3*2*1, степени 3, 2, 1, 0, число: 2³+3²+5¹+7⁰=360.
24=3*2*2*2, степени 2,1, 1, 1, число: 2²+3¹+5¹+7¹=420.
И дальше делаем аналогично.

Ну и в конце мы стоим перед не очень сложной задачкой:
Какое число из 8388608,  6144, 1152, 864, 525, 360, 420.... и т.д. наименьшее?
Ну, конечно же, 360, это и есть ответ к задаче.

[albom]

uses crt;
var n,n0:word;
    mn:array[1..128]of comp;
    pr:array[1..256]of longint;
    c:word;
    i:word;
    min:comp;
function power(a,b:comp):comp;
 var r:comp;
 begin
 r:=1;
 while b>0 do
  begin
  r:=r*a;b:=b-1;
  if r>=9.2e18/a then begin power:=0;exit end;
  end;
 power:=r;
 end;
procedure test(num:byte);
 var r,z:comp;
     k:byte;
 begin
 r:=1;
 for k:=1 to num do
  begin
  z:=power(pr[k],mn[k]-1);
  if z=0 then exit;
  r:=r*z;
  if r>=min then exit;
  end;
 min:=r;
 end;
 
procedure build(ind:byte;nn:word);near;
 var d:word;
 begin
 if nn=1 then
  begin
  test(ind-1);
  exit;
  end;
 for d:=2 to nn do
  begin
  if (ind>1)and(mn[ind-1]<d)then break;
  if nn mod d=0 then
   begin
   mn[ind]:=d;
   build(ind+1,nn div d);
   end;
  end;
 end;
label zzz;
begin
clrscr;
c:=1;
pr[1]:=2;
i:=3;
while c<256 do
 begin
 for n:=1 to c do
  if i mod pr[n]=0 then
   goto zzz;
 inc(c);
 pr[c]:=i;
 zzz:
 inc(i,2);
 end;
min:=9.2e18;
writeln('Введите кол-во делителей');
readln(n);
build(1,n);
if min=9.2e18 then
 writeln('Число с таким количеством делителей больше чем 9.2*10^18 !')
 else
 writeln('Минимальное число, у которого ровно ',n,' делителя: ',min:0:0);
readkey;
end.

[plan]

Ну вот и я про то же!  :D  :D

зы спасибо  ;)