Для заданного N указать меньше k такое, что все N чисел последовательности, начиная с Ak — одинаковые

@Aleks54321 · Регистрация: 24.03.2015

Author24 — интернет-сервис помощи студентам

В последовательности натуральных чисел A1, A2, A3, ... любое число Ak - наименьшее натуральное, которое делится без остатка на каждый из первых k натуральных чисел 1,2,3, .. k. Для заданного N указать меньше k такое, что все N чисел последовательности, начиная с Ak - одинаковые.

Входные данные: Натуральное число N (N <100).

Выходные данные: Ответ на задачу.

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

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

Пояснение: Начало ряда 1 2 6 12 60 60 420 840 2520 ...

Помогите,плиз.

@SpBerkut · 05.02.2016, 09:51

Для N = 79 k = 804212830686677669. Лютое задание. Табличка.

@Sergio Leone · 05.02.2016, 11:28

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

Для заданного N указать меньше k такое, что все N чисел последовательности, начиная с Ak - одинаковые

а растолкуйте мне, с чего это числа последовательности вдруг станут одинаковыми?!!

Добавлено через 1 минуту
я чего-то туплю.

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

Лютое задание. Табличка.

прости, а что это в табличке?

@SpBerkut · 05.02.2016, 11:58

Сообщение от Sergio Leone

а растолкуйте мне, с чего это числа последовательности вдруг станут одинаковыми?!!

Не все числа, а N чисел подряд. Каждый k-й член последовательности — НОК чисел от 1 до k. Тут коротенько об этом написано. Первое, что приходит мне в голову — перебирать все числа подряд, факторизируя каждое, накапливать множители НОК и сравнивать текущий НОК с множителями текущего числа. И считать промежутки, когда множители в НОК не добавляются. А множители добавляются с каждым новым простым числом и новой степенью простого числа, т.е. довольно часто. Поэтому перебирать нужно долго и упорно. Если бы N был ограничен хотя бы числом 75, то я бы сделал массив-константу с требуемыми значениями, тем паче, что условием это не возбраняется.

Сообщение от Sergio Leone

прости, а что это в табличке?

В таблице пары N — k.

Добавлено через 2 минуты
Именно поэтому я считаю задание лютым. Ведь при кажущейся простоте, оно требует походов в нудные, хотя и решаемые, дебри.

Добавлено через 7 минут
Более того, есть сомнения, что пройдёт фокус с факторизацией вещественных чисел. А их там приходится использовать, т.к. даже LongInt'а на всё не хватит.

@Sergio Leone · 05.02.2016, 13:26

SpBerkut, спасибо тебе большое, что ты пытаешься объяснить.
Тебя очень сильно затруднит ещё раз "разжевать" для особо тугих (я себя имею в виду), что дано и что требуется?!

ну вот, допустим,
есть последовательность чисел A1, A2, A3... (1, 2, 6, 12, 60, 60, 420, 840, 2520, 2520, 27720, 27720, 360360, 360360, 360360, 720720, 12252240, 12252240,...)

мы задаём N=2

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

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

почему результат равен 5 ?!

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

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

и ещё раз прошу извинить меня за несообразительность!

@SpBerkut · 05.02.2016, 13:32

Сообщение от Sergio Leone

почему результат равен 5 ?!

Потому что с пятого элемента начинается последовательность из двух одинаковых элементов (60). С 13-й позиции начинается последовательность из трёх одинаковых элементов (360360) и т.д.

@Sergio Leone · 05.02.2016, 21:29

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

Потому что с пятого элемента начинается последовательность из двух одинаковых элементов (60). С 13-й позиции начинается последовательность из трёх одинаковых элементов (360360) и т.д.

О. Спасибо большое. Теперь понял.

меня очень смущало слово "все": "такое, что все N чисел последовательности"
теперь я вижу, что задание то ли криво переведено, то ли своими словами кто-то коряво передал.
Нет однозначности и чёткости.
Если бы не твоя помощь, то я бы, наверное, его даже понять не сумел!
Как ты сумел увидеть суть вопроса - ума не приложу!

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

@SpBerkut · 05.02.2016, 21:45

Сообщение от Sergio Leone

я бы в сторону длинной арифметики смотрел

Я тоже смотрел бы туда. Но уж больно бессмысленно всё это. Для студентов слишком много ненужных заморочек — ограничьте вход тридцатью и уже можно решить с использованием базовых типов. А в реальной жизни задача не имеет практического применения. Могу предположить, что это какая-то олимпиада, но тут всё сводится к читу-массиву, который можно попробовать заранее сформировать каким-либо математическим пакетом, которому доступна длинная арифметика.

@Sergio Leone · 05.02.2016, 22:06

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

тут всё сводится к читу-массиву

Ага! я тоже о таком сразу подумал. но отбросил, как неспортивное решение, могут возникнуть проблемы при сдаче,
если эту задачу дал препод и он будет проверять решение. Хотя... Запрещение на такой массив в условии не вижу, есть повод, чтобы поспорить!

А вообще, согласен:

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

уж больно бессмысленно всё это. Для студентов слишком много ненужных заморочек — ограничьте вход тридцатью и уже можно решить с использованием базовых типов

В точку!

ФедосеевПавел · 05.02.2016, 22:11

Может быть сделать массив способом наподобие решета Эратосфена, в котором будут хранится количества простых делителей без учёта их степени (например, для 8 будет 1 делитель 2^3, а для 72 будет 2 делителя 2^3 и 3^2). А потом искать первую последовательность длины N следующего вида - 0, x, x...x, где число x>1.
Массив построить так

Pascal

const
  Nmax = 1000;
type
  TVector = array[1..Nmax] of byte;
var
  DivCount: TVector;
  i: integer;
  d: integer;
begin
  for i := low(DivCount) to high(DivCount) do
    DivCount[i] := 0;
  for i := 2 to high(DivCount) do
  begin
    if DivCount[i] <> 0 then
      continue;
    d := i + i;
    while d <= high(DivCount) do
    begin
      Inc(DivCount[d]);
      Inc(d, i);
    end;
  end;
  for i := low(DivCount) to high(DivCount) do
    Write(i: 4);
  writeln;
  for i := low(DivCount) to high(DivCount) do
    Write(DivCount[i]: 4);
  writeln;
end.

Я правда не могу пока оценить длину массива DivCount, возможно, даже и большая.

В этом массиве:
DivCount[i]=0 - когда i - простое число
DivCount[i]=1 - когда i - степень одного простого числа
DivCount[i]=t - когда i - раскладывается на t простых чисел разных степеней.

Почему я считаю возможным не подсчитывать степени простых делителей в разложении числа i - потому, что мы имеем НОК(1,..., i) и степени учлись ранее.

Сам массив сделал пока байтовым, потому, что произведение последовательных чисел очень быстро растёт, и первое число, имеющее хотя бы 7 простых делителей уже равно 2*3*5*7*11*13*17=510510.

@SpBerkut · 05.02.2016, 22:45

Сообщение от ФедосеевПавел

Может быть сделать массив способом наподобие решета Эратосфена

Неважно как будет это реализовано. При N порядка 80 организовать вывод уже проблема, т.к. значение даже в Extended не помещается по точности.

ФедосеевПавел · 05.02.2016, 22:53

Нет, это не верный подход, т.к. зависимость k от N очень быстро растёт

Код

N= 2, k=5
N= 3, k=13
N= 4, k=19
N= 5, k=53
N= 6, k=53
N= 7, k=211
N= 8, k=211
N= 9, k=211
N=10, k=72649
N=11, k=218971
N=12, k=218971
N=13, k=534077
N=14, k=55369651
N=15, k=964035871

И уже для N=99 (по условию N<100) массив не уместится в памяти.
Нужен другой подход.

@Sergio Leone · 05.02.2016, 23:07

Сообщение от ФедосеевПавел

И уже для N=99 (по условию N<100) массив не уместится в памяти.

прости, чего он в памяти не поместится?!
факториал числа 100 - это примерно 160 значное число.
массив:

Pascal

1 2	type str200=string[200]; var a:array[1..100] of str200;

даже ТурбоПаскаль "скушает" со своим ограничением на 64Кб сегментом, не говоря уже про нормальные компиляторы.

ФедосеевПавел · 05.02.2016, 23:16

Нет, я ошибся при расчётах. Нужно искать последовательность
0, x₂, x₃, ..., x_n
где x_i>1.

Тогда результат такой (правда считает долго)

Код

N= 2, k=5
N= 3, k=13
N= 4, k=19
N= 5, k=53
N= 6, k=53
N= 7, k=89
N= 8, k=89
N= 9, k=139
N=10, k=139
N=11, k=199
N=12, k=199
N=13, k=293
N=14, k=293
N=15, k=887
N=16, k=887
N=17, k=887
N=18, k=887
N=19, k=887
N=20, k=887
N=21, k=1129
N=22, k=1129
N=23, k=2477
N=24, k=2477
N=25, k=2477
N=26, k=2477
N=27, k=2971
N=28, k=2971
N=29, k=4297
N=30, k=4297
N=31, k=5591
N=32, k=5591
N=33, k=8467
N=34, k=8467
N=35, k=9551
N=36, k=9551
N=37, k=15683
N=38, k=15683
N=39, k=15683
N=40, k=15683
N=41, k=15683
N=42, k=15683
N=43, k=15683
N=44, k=15683
N=45, k=19609
N=46, k=19609
N=47, k=19609
N=48, k=19609
N=49, k=19609
N=50, k=19609
N=51, k=19609
N=52, k=19609
N=53, k=31397
N=54, k=31397
N=55, k=31397
N=56, k=31397
N=57, k=31397
N=58, k=31397
N=59, k=31397
N=60, k=31397
N=61, k=31397
N=62, k=31397
N=63, k=31397
N=64, k=31397
N=65, k=31397
N=66, k=31397
N=67, k=31397
N=68, k=31397
N=69, k=31397
N=70, k=31397
N=71, k=31397
N=72, k=31397
N=73, k=155921
N=74, k=155921
N=75, k=155921
N=76, k=155921
N=77, k=155921
N=78, k=155921
N=79, k=155921
N=80, k=155921
N=81, k=155921
N=82, k=155921
N=83, k=155921
N=84, k=155921
N=85, k=155921
N=86, k=155921
N=87, k=360653
N=88, k=360653
N=89, k=360653
N=90, k=360653
N=91, k=360653
N=92, k=360653
N=93, k=360653
N=94, k=360653
N=95, k=360653
N=96, k=360653
N=97, k=370261
N=98, k=370261
N=99, k=370261

И нет, в TurboPascal мой вариант не помещается.

Pascal

program Pas_090;
 
const
  Nmax = 370400;
type
  TVector  = array[1..Nmax] of byte;
  TInteger = dword;
var
  DivCount: TVector;
  i: TInteger;
  d: TInteger;
 
  N: integer;
  x: TInteger;
  Res: boolean;
begin
  {формирование массива}
  for i := low(DivCount) to high(DivCount) do
    DivCount[i] := 0;
  for i := 2 to high(DivCount) do
  begin
    if DivCount[i] <> 0 then
      continue;
    d := i + i;
    while d <= high(DivCount) do
    begin
      Inc(DivCount[d]);
      Inc(d, i);
    end;
  end;
  //  for i := low(DivCount) to high(DivCount) do
  //    Write(i: 4);
  //  writeln;
  //  for i := low(DivCount) to high(DivCount) do
  //    Write(DivCount[i]: 4);
  //  writeln;
 
 
  {поиск}
  for N := 2 to 99 do
  begin
 
    Res := False;
    for i := low(DivCount) to high(DivCount) - N do
    begin
      if DivCount[i] <> 0 then
        continue;
      x := DivCount[i + 1];
      if not (x > 1) then
        continue;
      Res := True;
      for d := i + 2 to i + N - 1 do
      begin
        Res := Res and ({x =} DivCount[d] > 1);
        if not Res then
          break;
      end;
      if Res then
      begin
        Writeln('N=', N: 2, ', k=', i);
        break;
      end;
    end;
    if not Res then
      break;
  end;
end.

Уменьшил размер массива с 10^9 до 320400 - стал считать почти мгновенно.

Добавлено через 2 минуты
Это не готовое решение для ТС. Это заготовка, но уже почти оформленная.

Добавлено через 2 минуты
Единственное но - не могу сравнить правильность результата хоть с каким-нибудь с эталоном.

@Sergio Leone · 05.02.2016, 23:18

ФедосеевПавел, ваши результаты не совпадают с таблицей из пост #2

ФедосеевПавел · 06.02.2016, 00:21

~~В той табличке приводится не минимальный номер Ak, а сами Ak.~~
Да, где-то я ошибся.

Добавлено через 59 минут
Думаю, что так - Нужно искать последовательность
0, x₂, x₃, ..., x_n
или
1, x₂, x₃, ..., x_n
где xi>1.
Тогда программа

Pascal

program Pas_090;
 
const
  Nmax = 370400;
type
  TVector  = array[1..Nmax] of byte;
  TInteger = dword;
var
  DivCount: TVector;
  i: TInteger;
  d: TInteger;
 
  N: integer;
  x: TInteger;
  Res: boolean;
begin
  {формирование массива}
  for i := low(DivCount) to high(DivCount) do
    DivCount[i] := 0;
  for i := 2 to high(DivCount) do
  begin
    if DivCount[i] <> 0 then
      continue;
    d := i + i;
    while d <= high(DivCount) do
    begin
      Inc(DivCount[d]);
      Inc(d, i);
    end;
  end;
  (*
  {вывод массива}
  for i := low(DivCount) to high(DivCount) do
    Write(i: 4);
  writeln;
  for i := low(DivCount) to high(DivCount) do
    Write(DivCount[i]: 4);
  writeln;
  *)
 
  {поиск}
  for N := 2 to 99 do
  begin
    Res := False;
    for i := low(DivCount) to high(DivCount) - N do
    begin
      if DivCount[i] > 1 then
        continue;
      x := DivCount[i + 1];
      if not (x > 1) then
        continue;
      Res := True;
      for d := i + 2 to i + N - 1 do
      begin
        Res := Res and (DivCount[d] > 1);
        if not Res then
          break;
      end;
      if Res then
      begin
        Writeln('N=', N: 2, ', k=', i);
        break;
      end;
    end;
    if not Res then
      break;
  end;
end.

Дает результат

Код

N= 2, k=5
N= 3, k=13
N= 4, k=19
N= 5, k=32
N= 6, k=53
N= 7, k=89
N= 8, k=89
N= 9, k=139
N=10, k=139
N=11, k=199
N=12, k=199
N=13, k=293
N=14, k=293
N=15, k=887
N=16, k=887
N=17, k=887
N=18, k=887
N=19, k=887
N=20, k=887
N=21, k=1129
N=22, k=1129
N=23, k=1331
N=24, k=1331
N=25, k=1331
N=26, k=1331
N=27, k=1331
N=28, k=1331
N=29, k=1331
N=30, k=1331
N=31, k=5591
N=32, k=5591
N=33, k=8467
N=34, k=8467
N=35, k=9551
N=36, k=9551
N=37, k=15683
N=38, k=15683
N=39, k=15683
N=40, k=15683
N=41, k=15683
N=42, k=15683
N=43, k=15683
N=44, k=15683
N=45, k=19609
N=46, k=19609
N=47, k=19609
N=48, k=19609
N=49, k=19609
N=50, k=19609
N=51, k=19609
N=52, k=19609
N=53, k=31397
N=54, k=31397
N=55, k=31397
N=56, k=31397
N=57, k=31397
N=58, k=31397
N=59, k=31397
N=60, k=31397
N=61, k=31397
N=62, k=31397
N=63, k=31397
N=64, k=31397
N=65, k=31397
N=66, k=31397
N=67, k=31397
N=68, k=31397
N=69, k=31397
N=70, k=31397
N=71, k=31397
N=72, k=31397
N=73, k=155921
N=74, k=155921
N=75, k=155921
N=76, k=155921
N=77, k=155921
N=78, k=155921
N=79, k=155921
N=80, k=155921
N=81, k=155921
N=82, k=155921
N=83, k=155921
N=84, k=155921
N=85, k=155921
N=86, k=155921
N=87, k=360653
N=88, k=360653
N=89, k=360653
N=90, k=360653
N=91, k=360653
N=92, k=360653
N=93, k=360653
N=94, k=360653
N=95, k=360653
N=96, k=360653
N=97, k=370261
N=98, k=370261
N=99, k=370261

В котором можно убедиться не по готовой последовательности k(N), а по исходной A(k) - https://oeis.org/A003418/b003418.txt (сюда я попал с https://oeis.org/A003418).
Видно, что при k=89 длина одинаковых A(k) равна 8, т.е. k(7)=k(8)=89. Аналогично и для k(9)=k(10)=139.

@SpBerkut · 06.02.2016, 09:12

Да. Вынужден признать, что поторопился с первым ответом. По всему видно, что ФедосеевПавел прав.

@Aleks54321 · 07.02.2016, 22:06 **[ТС]**

А как cделать,чтобы выводидись не все значения k при n от 1 до 99,а только при конкретном n?(ввели 2-получили 5,например)

@SpBerkut · 08.02.2016, 08:17

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

А как cделать,чтобы выводидись не все значения k при n от 1 до 99,а только при конкретном n?(ввели 2-получили 5,например)

Заюзать чит, описанный выше — предварительно прогнать все варианты и запихать их в массив.

ФедосеевПавел · 08.02.2016, 14:22

Pascal

program Pas_090;
 
const
  Nmax = 370400;
type
  TVector  = array[1..Nmax] of byte;
  TInteger = dword;
var
  N: integer;
  k: TInteger;
  DivCount: TVector;
  d: TInteger;
  Res: boolean;
begin
  readln(N);
  {формирование массива}
  for k := low(DivCount) to high(DivCount) do
    DivCount[k] := 0;
  for k := 2 to high(DivCount) do
  begin
    if DivCount[k] <> 0 then
      continue;
    d := k + k;
    while d <= high(DivCount) do
    begin
      Inc(DivCount[d]);
      Inc(d, k);
    end;
  end;
  {поиск}
  Res := False;
  for k := low(DivCount) to high(DivCount) - N do
  begin
    if DivCount[k] > 1 then
      continue;
    Res := True;
    for d := k + 1 to k + N - 1 do
    begin
      Res := Res and (DivCount[d] > 1);
      if not Res then
        break;
    end;
    if Res then
    begin
      writeln(k);
      break;
    end;
  end;
end.

Для заданного N указать меньше k такое, что все N чисел последовательности, начиная с Ak — одинаковые

Решение

Решение

@Aleks54321 1 / 1 / 0 Регистрация: 24.03.2015 Сообщений: 50
		1
	Для заданного N указать меньше k такое, что все N чисел последовательности, начиная с Ak — одинаковые 03.02.2016, 18:04. Показов 2754. Ответов 19 Метки нет (Все метки) В последовательности натуральных чисел A1, A2, A3, ... любое число Ak - наименьшее натуральное, которое делится без остатка на каждый из первых k натуральных чисел 1,2,3, .. k. Для заданного N указать меньше k такое, что все N чисел последовательности, начиная с Ak - одинаковые. Входные данные: Натуральное число N (N <100). Выходные данные: Ответ на задачу. Входные данные:2 Выходные данные:5 Пояснение: Начало ряда 1 2 6 12 60 60 420 840 2520 ... Помогите,плиз. 0

@SpBerkut Объявлятель переменных 1220 / 406 / 320 Регистрация: 24.09.2011 Сообщений: 1,265
	05.02.2016, 09:51	2
	Для N = 79 k = 804212830686677669. Лютое задание. Табличка. 0

@Sergio Leone 2509 / 1130 / 582 Регистрация: 07.06.2014 Сообщений: 3,286
	05.02.2016, 11:28	3
	Сообщение от Aleks54321 Для заданного N указать меньше k такое, что все N чисел последовательности, начиная с Ak - одинаковые а растолкуйте мне, с чего это числа последовательности вдруг станут одинаковыми?!! Добавлено через 1 минуту я чего-то туплю. Сообщение от SpBerkut Лютое задание. Табличка. прости, а что это в табличке? 0

@SpBerkut Объявлятель переменных 1220 / 406 / 320 Регистрация: 24.09.2011 Сообщений: 1,265
	05.02.2016, 11:58	4
	Сообщение от Sergio Leone а растолкуйте мне, с чего это числа последовательности вдруг станут одинаковыми?!! Не все числа, а N чисел подряд. Каждый k-й член последовательности — НОК чисел от 1 до k. Тут коротенько об этом написано. Первое, что приходит мне в голову — перебирать все числа подряд, факторизируя каждое, накапливать множители НОК и сравнивать текущий НОК с множителями текущего числа. И считать промежутки, когда множители в НОК не добавляются. А множители добавляются с каждым новым простым числом и новой степенью простого числа, т.е. довольно часто. Поэтому перебирать нужно долго и упорно. Если бы N был ограничен хотя бы числом 75, то я бы сделал массив-константу с требуемыми значениями, тем паче, что условием это не возбраняется. Сообщение от Sergio Leone прости, а что это в табличке? В таблице пары N — k. Добавлено через 2 минуты Именно поэтому я считаю задание лютым. Ведь при кажущейся простоте, оно требует походов в нудные, хотя и решаемые, дебри. Добавлено через 7 минут Более того, есть сомнения, что пройдёт фокус с факторизацией вещественных чисел. А их там приходится использовать, т.к. даже LongInt'а на всё не хватит. 1

@Sergio Leone 2509 / 1130 / 582 Регистрация: 07.06.2014 Сообщений: 3,286
	05.02.2016, 13:26	5
	SpBerkut, спасибо тебе большое, что ты пытаешься объяснить. Тебя очень сильно затруднит ещё раз "разжевать" для особо тугих (я себя имею в виду), что дано и что требуется?! ну вот, допустим, есть последовательность чисел A1, A2, A3... (1, 2, 6, 12, 60, 60, 420, 840, 2520, 2520, 27720, 27720, 360360, 360360, 360360, 720720, 12252240, 12252240,...) мы задаём N=2 Сообщение от Aleks54321 Входные данные:2 почему результат равен 5 ?! Сообщение от Aleks54321 Выходные данные:5 и ещё раз прошу извинить меня за несообразительность! 0

@SpBerkut Объявлятель переменных 1220 / 406 / 320 Регистрация: 24.09.2011 Сообщений: 1,265
	05.02.2016, 13:32	6
	Сообщение от Sergio Leone почему результат равен 5 ?! Потому что с пятого элемента начинается последовательность из двух одинаковых элементов (60). С 13-й позиции начинается последовательность из трёх одинаковых элементов (360360) и т.д. 1

@Sergio Leone 2509 / 1130 / 582 Регистрация: 07.06.2014 Сообщений: 3,286
	05.02.2016, 21:29	7
	Сообщение от SpBerkut Потому что с пятого элемента начинается последовательность из двух одинаковых элементов (60). С 13-й позиции начинается последовательность из трёх одинаковых элементов (360360) и т.д. О. Спасибо большое. Теперь понял. меня очень смущало слово "все": "такое, что все N чисел последовательности" теперь я вижу, что задание то ли криво переведено, то ли своими словами кто-то коряво передал. Нет однозначности и чёткости. Если бы не твоя помощь, то я бы, наверное, его даже понять не сумел! Как ты сумел увидеть суть вопроса - ума не приложу! Да, теперь, когдая понял задание, согласен, задачка весьма и весьма непростая... может я ошибаюсь, но я бы в сторону длинной арифметики смотрел. 0

@SpBerkut Объявлятель переменных 1220 / 406 / 320 Регистрация: 24.09.2011 Сообщений: 1,265
	05.02.2016, 21:45	8
	Сообщение от Sergio Leone я бы в сторону длинной арифметики смотрел Я тоже смотрел бы туда. Но уж больно бессмысленно всё это. Для студентов слишком много ненужных заморочек — ограничьте вход тридцатью и уже можно решить с использованием базовых типов. А в реальной жизни задача не имеет практического применения. Могу предположить, что это какая-то олимпиада, но тут всё сводится к читу-массиву, который можно попробовать заранее сформировать каким-либо математическим пакетом, которому доступна длинная арифметика. 1

@Sergio Leone 2509 / 1130 / 582 Регистрация: 07.06.2014 Сообщений: 3,286
	05.02.2016, 22:06	9
	Сообщение от SpBerkut тут всё сводится к читу-массиву Ага! я тоже о таком сразу подумал. но отбросил, как неспортивное решение, могут возникнуть проблемы при сдаче, если эту задачу дал препод и он будет проверять решение. Хотя... Запрещение на такой массив в условии не вижу, есть повод, чтобы поспорить! А вообще, согласен: Сообщение от SpBerkut уж больно бессмысленно всё это. Для студентов слишком много ненужных заморочек — ограничьте вход тридцатью и уже можно решить с использованием базовых типов В точку! 0

@SpBerkut Объявлятель переменных 1220 / 406 / 320 Регистрация: 24.09.2011 Сообщений: 1,265
	05.02.2016, 22:45	11
	Сообщение от ФедосеевПавел Может быть сделать массив способом наподобие решета Эратосфена Неважно как будет это реализовано. При N порядка 80 организовать вывод уже проблема, т.к. значение даже в Extended не помещается по точности. 0

ФедосеевПавел Модератор 8476 / 4335 / 1642 Регистрация: 01.02.2015 Сообщений: 13,461 Записей в блоге: 8
	05.02.2016, 22:53	12
	Нет, это не верный подход, т.к. зависимость k от N очень быстро растёт Код N= 2, k=5 N= 3, k=13 N= 4, k=19 N= 5, k=53 N= 6, k=53 N= 7, k=211 N= 8, k=211 N= 9, k=211 N=10, k=72649 N=11, k=218971 N=12, k=218971 N=13, k=534077 N=14, k=55369651 N=15, k=964035871 И уже для N=99 (по условию N<100) массив не уместится в памяти. Нужен другой подход. 0

@Sergio Leone 2509 / 1130 / 582 Регистрация: 07.06.2014 Сообщений: 3,286
	05.02.2016, 23:18	15
	ФедосеевПавел, ваши результаты не совпадают с таблицей из пост #2 0

@SpBerkut Объявлятель переменных 1220 / 406 / 320 Регистрация: 24.09.2011 Сообщений: 1,265
	06.02.2016, 09:12	17
	Да. Вынужден признать, что поторопился с первым ответом. По всему видно, что ФедосеевПавел прав. 0

@Aleks54321 1 / 1 / 0 Регистрация: 24.03.2015 Сообщений: 50
	07.02.2016, 22:06 [ТС]	18
	А как cделать,чтобы выводидись не все значения k при n от 1 до 99,а только при конкретном n?(ввели 2-получили 5,например) 0

@SpBerkut Объявлятель переменных 1220 / 406 / 320 Регистрация: 24.09.2011 Сообщений: 1,265
	08.02.2016, 08:17	19
	Сообщение от Aleks54321 А как cделать,чтобы выводидись не все значения k при n от 1 до 99,а только при конкретном n?(ввели 2-получили 5,например) Заюзать чит, описанный выше — предварительно прогнать все варианты и запихать их в массив. 0