Мандарины. Остатки от делений.

[faradey]

На праздник 8 марта ребята решили сделать подарки девушкам. Готовя подарки, они разложили в каждый подарок по открытке и по мягкой игрушке. А когда начали раскладывать мандарины, то возникло осложнение. Сначала они разложили мандарины по m штук в каждый пакет (в другие пакеты - яблоки), оказалось, что в одном из пакетов m - 1 мандарин, когда положили по m - 1 мандарин, осталось m - 2, попытались положить по m - 2 мандарин , осталось m - 3, и т.д., когда попытались положить по 2 мандарина, то остался 1 мандарин. Какую же количество мандарин закупили ребята?

program new;
uses crt;
var
m,n,i:integer;
begin
clrscr;
read(m);
for i:=1 to 1000 do begin
if (i mod m=m-1) and  (i mod m-1=m-2) and  ((i mod m-2)=m-3) and  (i mod 2<>0) and (i>m) then  begin
writeln(i); break; end;
end;

readkey;
end.

набросал что то, накажется набросал бред, может условие не так понял, буду благодарен за помощь

[faradey]

есть идеи?

[Thunder Dragon]

Сообщение от faradey

есть идеи?

я сколько б не пытался - не могу понять условия задачи... ПС: ты же заоную олимпиаду кибернетики (универ Шевченка) решаешь, да? =)

[VIK_aka_TOR]

подправил малость код...

var
m,n,i:integer;
begin
For m:=5 to 1000 do
for i:=1 to 1000 do begin
if ((i mod m) = (m - 1)) and ( (i mod (m - 1)) = (m - 2) ) and ((i mod (m - 2)) = (m - 3) ) and (( i mod 2) = 1) then  begin
writeln('мандарин ',i,'; m - ', m); end;
end;
end.

ответы такие:

мандарин 59; m - 5
мандарин 119; m - 5
мандарин 179; m - 5
мандарин 239; m - 5
мандарин 299; m - 5
мандарин 359; m - 5
мандарин 419; m - 5
мандарин 479; m - 5
мандарин 539; m - 5
мандарин 599; m - 5
мандарин 659; m - 5
мандарин 719; m - 5
мандарин 779; m - 5
мандарин 839; m - 5
мандарин 899; m - 5
мандарин 959; m - 5
мандарин 59; m - 6
мандарин 119; m - 6
мандарин 179; m - 6
мандарин 239; m - 6
мандарин 299; m - 6
мандарин 359; m - 6
мандарин 419; m - 6
мандарин 479; m - 6
мандарин 539; m - 6
мандарин 599; m - 6
мандарин 659; m - 6
мандарин 719; m - 6
мандарин 779; m - 6
мандарин 839; m - 6
мандарин 899; m - 6
мандарин 959; m - 6
мандарин 209; m - 7
мандарин 419; m - 7
мандарин 629; m - 7
мандарин 839; m - 7
мандарин 167; m - 8
мандарин 335; m - 8
мандарин 503; m - 8
мандарин 671; m - 8
мандарин 839; m - 8
мандарин 503; m - 9
мандарин 359; m - 10
мандарин 719; m - 10
мандарин 989; m - 11
мандарин 659; m - 12

если я правильно понял задание... то все сходится)))

[Serge_Bliznykov]

ответы такие:

Вы неправы (возможно, вы решали какую-то ДРУГУЮ задачу ) !

ответы получаются такие:

m= 2  Число мандарин N = 1
m= 3  Число мандарин N = 5
m= 4  Число мандарин N = 11
m= 5  Число мандарин N = 59
m= 6  Число мандарин N = 59
m= 7  Число мандарин N = 419
m= 8  Число мандарин N = 839
m= 9  Число мандарин N = 2519
m= 10  Число мандарин N = 2519
m= 11  Число мандарин N = 27719
m= 12  Число мандарин N = 27719
m= 13  Число мандарин N = 360359
m= 14  Число мандарин N = 360359
m= 15  Число мандарин N = 360359
m= 16  Число мандарин N = 720719
m= 17  Число мандарин N = 12252239
m= 18  Число мандарин N = 12252239

получил я это с помощью такого кода:

function NOD (a,b:longint):longint;
begin
while a<>b do
  if (a>b) then a:=a-b else b:=b-a;
NOD:=a;
end;


function nok(Num1, Num2: longint):longint;
begin
  if Num1*Num2 = 0 then NOK:= Num1+Num2
  else
      NOK:= trunc(Num1*Num2/NOD(Num1,Num2));
end;


var
  i, myNOK : longint;
  m : integer;
begin
  for m := 2 to 18 do begin
    myNOK := 1;
    for i:=m downto 2 do myNOK := nok(myNOK, i);
    WriteLn('m= ',m,'  Число мандарин N = ',myNOK-1);
  end;
  Readln
end.

ещё есть решение (с) Puporev отсюда

uses crt;
var m,n,i,k:longint;
    f:boolean;
begin
clrscr;
write('m=');
readln(m);
n:=1;
f:=false;
while not f do
 begin
  k:=0;
  for i:=2 to m do
  if n mod i=i-1 then k:=k+1;
  if k=m-1 then f:=true
  else n:=n+2;{только нечетные}
 end;
 writeln('при m=',m,' получаем n=',n);
readln
end.

ну и обсуждение этой задачи
можно посмотреть:
Тут
или
тут (хотя в этой теме путаников и путаницы много)


а по сути всё просто, нужно найти НОК от чисел (1,2,3, m-1)
от полученного НОК нужно вычести единичку. и это будет ответом на задачу.
НО!
но проблема в том, что если рассматривать эту задачу как олимпиадную
(смотри условие задачи - "Подарки к 8 Марта"), то там задано ограничение на входные данные:

Количество мандарин m (1 < m ≤ 1000), которое хотели ребята вначале положить в подарок.

а это означает, что в процессе вычисления, просто так взять и перемножить все числа, чтобы найти их НОК не получится, ибо:

для М больших 20 не хватает лонгинта, а для М больше 43 - инт64

и нужно использовать какой-то другой алгоритм получения НОК. я лично этот алгоритм придумать не смог, поэтому эту задачу решить не смог...

[VIK_aka_TOR]

нашел недочет со своей стороны... пренебрег "и т.д."... тобишь бала лишь проверка на

то в одном из пакетов m - 1 мандарин, когда положили по m - 1 мандарин, осталось m - 2, попытались положить по m - 2 мандарин , осталось m - 3

ну и нечетность... когда по 2 и остался 1... впредь буду повнимательнее...

[Plague]

To Serge_Bliznykov
Я бы поменял две функции для быстрого вычисления в Вашей программе,
сделал бы так:

function nod(a,b:int64):int64;
begin
  if b = 0 then nod:=a else nod:=nod(b,a mod b)
end; 

function nok(a,b:int64):int64;
begin
  if a*b=0 then nok:= a+b else nok:=a*b div nod(a,b);
end;

[Plague]

При m=10 000 ответ содержит 4349 цифры, мой компьютер считает за 3.765 секунд (в программе 80 строк кода). A при m=1 000, 433 цифры в ответе, считает за 0.031 секунду.
Чуть чуть теории чисел, длинной арифметики и все.
Суть алгоритма использовать каноническое разложение числа на множителичитать тут
и с помощью него вычислять НОК читать тут

[Serge_Bliznykov]

Сообщение от Plague

Чуть чуть теории чисел, длинной арифметики и все.

ага, значит всё таки - длинная арифметика... а я думал, что можно обойтись без неё - что она по времени не пройдёт.. видимо, ошибался...

Сообщение от Plague

Суть алгоритма использовать каноническое разложение числа на множителичитать тут
и с помощью него вычислять НОК читать тут

Большое спасибо!

[Plague]

Тут длинная арифметика "усеченная".
Нужно длинное число умножать на integer:

const dd='0123456789';
function mul(a:string;b:integer):string;
var s,q:string;
    i,x,y,u,p:longint;
begin
  u:=0;
  s:='';
  q:='';
  for i:=length(a) downto 1 do 
    begin
      x:=pos(a[i],dd)-1;
      p:=x*b+u;
      y:=p mod 10;
      u:=p div 10;
      s:=dd[y+1]+s;
    end;
  if u>0 then str(u,q);
  mul:=q+s;
end;

и из длинного числа вычесть 1:

const dd='0123456789';
function sub1(a:string):string;
var i:integer;
begin
  i:=length(a);
  while a[i]='0' do
    begin
      a[i]:='9';
      dec(i);
    end;
    a[i]:=dd[pos(a[i],dd)-1];
    sub1:=a;
end;

Так что время выполнение "быстрое"