Недавно алексей устроился на работу в крупную it-компанию. ему предложили поработать над
групповым проектом. до этого у него уже было много успешных проектов, но в этот раз всё шло
не по плану.
алексей долго пытался найти причину всех неудач. в итоге он пришел к выводу, что его группа
. он считает, что i-й человек в компании характеризуется числом ai
. тогда в его
понимании, группа , если для любого целого m > 1 и любой пары разных людей
(i, j) в группе верно, что остатки от деления чисел ai и aj на m различаются.
алексей обратился со своими соображениями к руководству. они были бы рады согласиться на
реформы, но для начала хотели бы оценить все риски. алексею убедить руководство, для
этого требуется найти минимальное количество групп, на которое можно разбить
всех работников компании.
формат входных данных
в первой строке задано одно целое число n (2 6 n 6 200 000) — количество работников в компании.
во второй строке заданы n целых чисел a1, a2, . . , an (1 6 ai 6 109
) — числа, характеризующие
работников.
формат выходных данных
выведите одно число — минимальное количество групп, на которое можно
разбить всех работников компании.
примеры
стандартный ввод стандартный вывод
4
1 2 3 1
3
5
6 1 2 5 3
3
6
1 1 2 2 1 1
4
замечание
в первом примере работников можно разбить на группы первый и третий работник не могут быть в одной группе
так как остатки от деления a1 и a3 на 2 . первый и четвёртый работник не могут быть
в одной группе так как остатки от деления a1 и a4 на 7 . третий и четвёртый работник
не могут быть в одной группе так как остатки от деления a3 и a4 на 2 . таким образом,
ответ на данный тест равен 3
const
n=10;
var
a:array[1..n] of integer;
i,x,k,j,s:integer;
begin
randomize:
for i:=1 to n do a[i]:=random(255); {формируем случайный массив}
for i:=1 to n do write(a[i],' '); {выводим этот массив его на экран}
writeln('x='); read(x); {вводим x, в программе}
for i:=1 to n do If x=a[i] {если х=a[i] тогда}
then for j:=i to n do {начинаем новый цикл с i до n}
S:=S+a[j]; {вычисляем сумму}
writeln(S);
end;
Вряд ли пополнит ваши знания, к примеру, такой вот текст, взятый, из математической энциклопедии: «Резонанс – явление увеличения амплитуды вынужденных колебаний при приближении частоты внешнего воздействия к одной из частот собственных колебаний динамической системы». Таким образом, информация понятна, если она выражена на языке доступном для получателя. Вместе с тем, совершенно понятное сообщение «Треугольник – фигура, имеющая три угла и три стороны» не расширяет ваши знания.Оно для вас неинформативно, хотя это же сообщение будет нести информацию для учеников 1 класса.;