5. Целочисленная арифметика
Напомним некоторые термины. Натуральными числами называют целые положительные числа. Натуральное число называется простым, если делится без остатка только на 1 и само на себя. Иначе число называется составным. Число 2 является единственным четным простым числом.
Начнем с распространенной задачи. Требуется определить, является ли заданное натуральное число N простым.
Можно последовательно перебирать вероятные делители 2, 3, …, N-1. Если N не делится ни на одно из этих чисел, то оно простое. Как уменьшить объем вычислений?
Во-первых, достаточно проверять делимость на числа от 2 до K = [ √N ], где квадратными скобками обозначена целая часть числа. Действительно, если один из делителей больше K, то второй должен быть меньше K.
Во-вторых, нет необходимости проверять четные числа, большие 2: они составные. А для нечетных чисел достаточно исследовать только нечетные делители.
Описанный подход реализуется следующей функцией:
Function Isprime(N: longint): boolean;
{Возвращает true для простого N, false для составное}
Var
i, k: integer;
Flag: boolean;
Begin
k:=Trunc(Sqrt(N));
Flag:=true; {признак простого числа}
if (not Odd(N)) and (N<>2) then Flag:=false
else
begin
i:=3;
While i<=k do
if (N mod i)=0 then
begin
Flag:=false;
Break; {N-составное}
end
else i:=i+2;
end;
Isprime:=Flag;
End;
Несколько усложним задачу. Пусть сейчас требуется вывести все простые числа от M до N, где M ≤ N ≤ 106, а время счета не должно превышать 2 сек. Описанный выше подход не укладывается в это ограничение.
Будем для каждого числа проверять делимость не на все числа до корня из этого числа, а только на простые числа. Их может быть не более 1000, поэтому легко найти их заранее и поместить в массив.
Два натуральных числа называют взаимно простыми, если они не имеют общих делителей, больших 1. Взаимную простоту двух чисел X и Y легко проверить путем нахождения их наибольшего общего делителя НОД(X, Y). Если он оказывается равным 1, то числа взаимно просты.
Максимальное сокращение дроби X / Y возможно на величину НОД(X, Y).
Приведем без доказательства свойства наибольшего общего делителя:
1) НОД(X, Y) = X, если Y = 0;
2) НОД(X, Y) = X, если X = Y;
3) НОД(X, Y) = НОД(Y, X);
4) НОД(X, Y) = НОД(X - Y, Y), если X > Y.
На этих свойствах основан алгоритм Евклида нахождения НОД(X, Y). Например,
НОД(12, 9) = НОД(3, 9) = НОД(9, 3) = НОД(6, 3) = НОД(3, 3) = 3.
При большом X и малом Y последнее свойство будет использоваться много раз. Более современная версия алгоритма Евклида основана на том, что при Y ≠ 0 и X ≥ Y выполняется свойство НОД(X, Y) = НОД(Y, X mod Y). Приведем фрагмент программы вычисления НОД(X, Y).
While Y>0 do
Begin
Z:=X mod Y;
X:=Y;
Y:=Z;
End; {ответ в X}
Более эффективный алгоритм поиска НОД, не требующий трудоемкой операции деления по модулю, приведен в [3].
В ряде приложений используется наименьшее общее кратное двух чисел НОК(X, Y), связанное с НОД(X, Y) простым соотношением: НОК(X, Y) = (X×Y) / НОД(X, Y).
Греческому математику Эратосфену, жившему до нашей эры, принадлежит алгоритм нахождения простых чисел в заданном диапазоне. Из всех чисел последовательно удаляются те, которые делятся на 2, на 3 и т. д. В итоге остаются только простые числа. Такой способ называют методом «решета» [4].
Рассмотрим для примера следующую задачу.
Окраска чисел. Профессор Психовецкий решил покрасить все числа от 1 до N (1 ≤ N ≤109) так, чтобы каждые два числа A и B имели разный цвет, если A делится на B. Каким минимальным количеством цветов можно обойтись?
Ввод. В единственной строке файла INPUT. TXT задано число N (1 ≤ N ≤10000).
Вывод. В единственную строку OUTPUT. TXT вывести минимальное количество цветов.
Примеры
Ввод 1 Ввод 2 Ввод 3
3 5 12
Вывод 1 Вывод 2 Вывод 3
2 3 4
Можно решать задачу перебором, рассматривая по возрастанию возможные делители чисел до N включительно. Такой способ реализуется следующим образом.
Program Paint;
Const Max=1000000;
Var
M, N,i, j: longint;
Color: array [1..Max] of byte; {номера цветов}
Fin, Fout: text;
begin
Assign(Fin,'input. txt');
Reset(Fin);
ReadLn(Fin, N);
Close(Fin);
For i:=1 to N do Color[i]:=1; {инициализация}
M:=1; {число цветов и максимальный номер цвета}
For i:=2 to N do {i-число для окраски}
For j:=1 to i div 2 do {j-предполагаемый делитель}
if (i mod j = 0) and (Color[i]=Color[j]) then
begin
Color[i]:=Color[i]+1;
if Color[i]>M then M:=M+1;
end;
Assign(Fout,'output. txt');
Rewrite(Fout);
WriteLn(Fout, M);
Close(Fout);
End.
Метод имеет квадратичную трудоемкость, поэтому непригоден при больших значениях N. Опишем другой подход. В соответствии с методом Эратосфена более рационально перекрашивать последовательно все числа, имеющие общий делитель. Для этого достаточно переписать цикл окраски в следующем виде.
For i:=1 to N div 2 do {i-первый сомножитель}
For j:=2 to N div i do {j-второй сомножитель}
Begin
k:=i*j;
if Color[k]=Color[i] then Color[k]:=Color[i]+1;
if Color[k]>M then M:=Color[k];
end;
Цикл вычислений повторяется последовательно N, [N / 2], [N / 3], …, [N / ([N / 2])] раз, где квадратными скобками обозначена целая часть числа. Можно показать, что общее количество повторений оценивается величиной O(NLog2N).
Задачи для самостоятельного решения
5.1. Размещение (4)
В массив A1, A2,…, AN помещены числа 2, 3,..., N+1 так, что каждое значение Ai делится на i. Сколько способов такого размещения?
Ввод из файла INPUT. TXT. В единственной строке вводится значение N.
Вывод в файл OUTPUT. TXT. В единственной строке выводится количество вариантов размещения.
Примеры
Ввод 1 Ввод 2 Ввод 3
6 3 11
Вывод 1 Вывод 2 Вывод 3
1 2 8
5.2. Колесо Фортуны (5)
Развлекательный телеканал транслирует шоу «Колесо Фортуны». В процессе игры участники шоу крутят большое колесо, разделенное на сектора. В каждом секторе этого колеса записано число. После того как колесо останавливается, специальная стрелка указывает на один из секторов. Число в этом секторе определяет выигрыш игрока.
Участник шоу заметил, что колесо в процессе вращения замедляется из-за того, что стрелка задевает за выступы на колесе, находящиеся между секторами. Если колесо вращается с угловой скоростью v градусов в секунду, и стрелка, переходя из сектора X к следующему сектору, задевает за очередной выступ, то текущая угловая скорость движения колеса уменьшается на k градусов в секунду. При этом если v ≤ k, то колесо не может преодолеть препятствие и останавливается. Стрелка в этом случае будет указывать на сектор X.
Участник шоу собирается вращать колесо. Зная порядок секторов на колесе, он хочет заставить колесо вращаться с такой начальной скоростью, чтобы после остановки колеса стрелка указала на как можно большее число. Колесо можно вращать в любом направлении и придавать ему начальную угловую скорость от a до b градусов в секунду.
Требуется написать программу, которая по заданному расположению чисел в секторах, минимальной и максимальной начальной угловой скорости вращения колеса и величине замедления колеса при переходе через границу секторов вычисляет максимальный выигрыш.
Ввод из файла INPUT. TXT. Первая строка входного файла содержит целое число N — количество секторов колеса (3 ≤ N ≤ 100). Вторая строка входного файла содержит N положительных целых чисел, каждое из которых не превышает 1000 - числа, записанные в секторах колеса. Числа приведены в порядке следования секторов по часовой стрелке. Изначально стрелка указывает на первое число. Третья строка содержит три целых числа: a, b и k (1 ≤ a ≤ b ≤ 109, 1 ≤ k ≤ 109).
Вывод в файл OUTPUT. TXT. В выходном файле должно содержаться одно целое число — максимальный выигрыш.
Пояснения к примерам. В первом примере возможны следующие варианты: можно придать начальную скорость колесу равную 3 или 4, что приведет к тому, что стрелка преодолеет одну границу между секторами, или придать начальную скорость равную 5, что позволит стрелке преодолеть 2 границы между секторами. В первом варианте, если закрутить колесо в одну сторону, то выигрыш получится равным 2, а если закрутить его в противоположную сторону, то -5. Во втором варианте, если закрутить колесо в одну сторону, то выигрыш будет равным 3, а если в другую сторону, то - 4. Во втором примере возможна только одна начальная скорость вращения колеса - 15 градусов в секунду. В этом случае при вращении колеса стрелка преодолеет семь границ между секторами. Тогда если его закрутить в одном направлении, то выигрыш составит 4, а если в противоположном направлении, то - 3. Наконец, в третьем примере оптимальная начальная скорость вращения колеса равна 2 градусам в секунду. В этом случае стрелка вообще не сможет преодолеть границу между секторами, и выигрыш будет равен 5.
Пример
Ввод 1 Ввод 2 Ввод 3
5 5 5 7 3
1 2 3 4 5 1 2 3 4 5 5 4 3 2 1
3 5 2 15 15 2 2 5 2
Вывод 1 Вывод 2 Вывод 3
5 4 5
5.3. Упорядоченные дроби (6)
Требуется написать программу, которая выводит в порядке возрастания все несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают N.
Ввод из файла INPUT. TXT. Входной файл содержит целое число N (2 ≤ N ≤ 1000).
Вывод в файл OUTPUT. TXT. В выходной файл необходимо вывести все дроби по одной в каждой строке.
Пример
Ввод
5
Вывод
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
5.4. Дели
Будем называть нормальным набор из k чисел (a1, a2, …, ak), если выполнены следующие условия:
1) каждое из чисел ai является делителем числа N;
2) выполняется неравенство a1 < a2 < … < ak;
3) числа ai и ai+1 для всех i от 1 до k – 1 являются взаимно простыми;
4) произведение a1a2…ak не превышает N.
Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.
Требуется написать программу, которая по заданным значениям N и k определяет количество нормальных наборов из k делителей числа N.
Ввод из файла INPUT. TXT. Первая строка входного файла содержит два целых числа: N и k (2 ≤ N ≤ 108, 2 ≤ k ≤ 10).
Вывод в файл OUTPUT. TXT. В выходном файле должно содержаться одно число — количество нормальных наборов из k делителей числа N.
Примеры
Ввод 1 Ввод 2
90 3 10 2
Вывод 1 Вывод 2
16 4
5.5. Кастинг (4)
В театре работает n актеров. Известно, что среди них a – высоких, b – голубоглазых и с – блондинов. Для главной роли в новом спектакле режиссеру требуется только один высокий голубоглазый блондин. Чтобы спланировать свое время для беседы с каждым таким артистом из труппы театра, режиссеру необходимо узнать, какое максимальное или какое минимальное количество артистов из работающих в театре подходит для этой роли.
Требуется написать программу, которая по заданным числам n, a, b и с определяет минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.
Ввод. Первая строка входного файла INPUT. TXT содержит одно число, которое задает, минимальное или максимальное количество актеров необходимо найти в данном тесте. Это число может принимать следующие значения:
· 1 - если в данном тесте требуется определить минимальное количество актеров;
· 2 - если в данном тесте требуется определить максимальное количество актеров.
Вторая строка входного файла содержит разделенные пробелами четыре целых числа: n, a, b, с (1 ≤ n ≤ 10 000, 0 ≤ a ≤ n, 0 ≤ b ≤ n, 0 ≤ c ≤ n).из файла INPUT. TXT.
Вывод. Выходной файл OUTPUT. TXT должен содержать одно число – минимальное или максимальное (в зависимости от входных данных) количество актеров, которые могут претендовать на главную роль в новом спектакле. в файл.
Примеры
Ввод 1 Ввод 2
2 1
5 3 4 5 5 3 4 5
Вывод 1 Вывод 2
3 2
Основные порталы (построено редакторами)