Целочисленная арифметика

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;

Задачи для самостоятельного решения

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. Колесо Фортуны (4)

Развлекательный телеканал транслирует шоу «Колесо Фортуны». В процессе игры участники шоу крутят большое колесо, разделенное на сектора. В каждом секторе этого колеса записано число. После того как колесо останавливается, специальная стрелка указывает на один из секторов. Число в этом секторе определяет выигрыш игрока.

Участник шоу заметил, что колесо в процессе вращения замедляется из-за того, что стрелка задевает за выступы на колесе, находящиеся между секторами. Если колесо вращается с угловой скоростью v градусов в секунду, и стрелка, переходя из сектора X к следующему сектору, задевает за очередной выступ, то текущая угловая скорость движения колеса уменьшается на k градусов в секунду. При этом если v ≤ k, то колесо не может преодолеть препятствие и останавливается. Стрелка в этом случае будет указывать на сектор X.

Участник шоу собирается вращать колесо. Зная порядок секторов на колесе, он хочет заставить колесо вращаться с такой начальной скоростью, чтобы после остановки колеса стрелка указала на как можно большее число. Колесо можно вращать в любом направлении и придавать ему начальную угловую скорость от a до b градусов в секунду.

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

Ввод из файла INPUT. TXT. Первая строка входного файла содержит целое число N — количество секторов колеса (3 ≤ N ≤ 100).

Вывод в файл OUTPUT. TXT. В выходном файле должно содержаться одно целое число — максимальный выигрыш.

Пример

Ввод 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 ≤ 255).

Вывод в файл 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

6. Длинная арифметика

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

Ниже приводится простой вариант процедур и функций длинной арифметики [2]. Такой подход неэкономичен как по памяти, так и по скорости. Память используется неэффективно, так как для записи каждой цифры используется полный байт. Длина числа не хранится, а находится при вычислениях либо просто не используется, что снижает скорость. К тому же все вычисления производятся в десятичной системе счисления. В системах счисления с основанием 2 операции целочисленного деления и нахождения остатка можно свести к битовым операциям сдвигов, которые выполняются быстрее. Тем не менее, приводимый вариант реализации длинной арифметики пригоден для большинства практических задач и прост в применении. Более полное описание проблем, связанных с длинной арифметикой, можно найти в [3].

Const

numlen = <максимальное количество знаков в длинных числах>;

{ для параметров циклов используются переменные integer,

если numlen>MaxInt, нужно использовать переменные типа word }

Type

number=array[1..numlen] of byte;

{ длинное число от младших разрядов к старшим;

переменной A типа number представлено число SUM(a[i]*10^(i-1))}

Procedure Set0(var n:number); {обнуление длинного числа}

Var

i: integer;

Begin

For i:=1 to numlen do

n[i]:=0;

End;

Procedure SetN(Var n: number; short: integer);

{занесение короткого числа в длинное}

Var

i: integer;

Begin

Set0(n); i:=1;

While short>0 do

begin

n[i]:=short mod 10;

short:=short div 10;

i:=i+1;

end;

End;

Procedure Move(n1:number; Var n2:number);

{пересылка длинного числа n2:=n1}

Var

i: integer;

Begin

For i:=1 to numlen do

n2[i]:=n1[i];

End;

Function Len(var n:number): integer;

{получение длины числа, для нуля длина 1 }

Var

i: integer;

Begin

For i:=numlen downto 1 do

if n[i]<>0 then

begin

Len:=i;

Exit;

end;

Len:=1;

End;

Procedure Show(var n:number);

{вывод числа и перевод строки }

Var

i: integer;

Begin

For i:=Len(n) downto 1 do

Write(n[i]);

WriteLn;

End;

Procedure AddShort(Var n: number; short: integer);

{прибавление короткого числа}

Var

i: integer;

Begin

i:=1;

While short>0 do

begin

short:=short+n[i];

n[i]:=short mod 10;

short:=short div 10;

i:=i+1;

end;

End;

Procedure MulShort(Var n: number; short: integer);

{умножение на короткое число}

Var

i, carry: integer;

Begin

carry:=0;

For i:=1 to numlen do

begin

carry:=carry+n[i]*short;

n[i]:=carry mod 10;

carry:=carry div 10;

end;

if carry<>0 then {диагностика переполнения}

Halt(1);

End;

Procedure DivShort(Var n: number; divisor: integer; Var rem: integer);

{деление на короткое число и получение остатка}

Var

i: integer;

Begin

rem:=0;

For i:=numlen downto 1 do

begin

rem:=rem*10+n[i];

n[i]:=rem div divisor;

rem:=rem mod divisor;

end;

End;

Procedure Add(Var n1,n2: number);

{прибавление длинного числа}

Var

i, carry: integer;

Begin

carry:=0;

For i:=1 to numlen do

begin

carry:=carry+n1[i]+n2[i];

n1[i]:=carry mod 10;

carry:=carry div 10;

end;

if carry<>0 then {диагностика переполнения}

Halt(1);

End;

Procedure Mul(Var n1,n2: number; Var n3: number);

{умножение длинных чисел}

Var

i1,i2,i3,len1,len2,carry: integer;

Begin

Set0(n3);

len1:=Len(n1);

len2:=Len(n2);

For i1:=1 to len1 do

For i2:=1 to len2 do

begin

i3:=i1+i2-1;

carry:=n1[i1]*n2[i2];

While carry>0 do

begin

carry:=carry+n3[i3];

n3[i3]:=carry mod 10;

carry:=carry div 10;

inc(i3);

end;

end;

End;

Function Cmp(Var n1,n2: number): integer;

{ сравнение чисел:

если n1<n2 выдает -1

если n1=n2 выдает 0

если n1>n2 выдает 1

}

Var

i: integer;

Begin

For i:=numlen downto 1 do

begin

if n1[i]<n2[i] then

begin

Cmp:=-1;

Exit;

end;

if n1[i]>n2[i] then

begin

Cmp:=1;

Exit;

end;

end

Cmp:=0;

End;

Рассмотрим для примера задачу, связанную с применением длинной арифметики.

Маг. Имеется N супружеских пар. Маг должен определить, кто кому супруг. Какова вероятность угадать ровно K раз из N?

Ввод из файла INPUT. TXT. В первой задаются через пробел строке K и N (1 ≤ N ≤ 100, 0 ≤ K ≤ N).

Вывод в файл OUTPUT. TXT вероятности угадать ровно K раз из N в виде несократимой дроби либо единственного значения 0.

Примеры

Ввод 1 Ввод 2

2 5 9 10

Вывод 1 Вывод 2

1/6 0

Пронумеруем, например, мужчин от 1 до N. Сейчас нужно найти вероятность такого расположения женщин в позициях от 1 до N, чтобы ровно K из них соответствовали позиции своего мужа.

Пусть D(N) – функция, определяющая количество перестановок из N элементов 1, 2, …, N, в которых ни один из элементов не остается на своем месте. Такие перестановки называются беспорядками. Тогда ответ задачи определяет выражение

PNK = (CNK ´ D(N-K)) / N! = D(N-K)) / K! (N-K)! (1)

Действительно, для каждого набора из K элементов, остающихся на своих местах, существуют D(N-K) перестановок остальных элементов, а общее число перестановок N! Остается найти способ вычисления функции D(N).

Очевидно, что D(1) = 0, D(2) = 1, D(3)=2 - перестановки (2, 3, 1) и (3, 1, 2).

При N = 4 существуют 9 перестановок с элементами не на своих местах:

(2, 1, 4, 3), (2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3),

(4, 3, 1, 2), (4, 3, 2, 1), т. е. D(4)=9.

Докажем приведенную в [1] без доказательства рекуррентную формулу

D(N+1) = N ´ ( D(N) + D(N-1)) (2)

Возможны два варианта:

1.  Элемент N+1 находится на месте K, а элемент K находится на месте N+1, то есть перестановка образована обменом элемента N+1 c элементом K. Тогда все остальные N-1 элементов не на своих местах. Поскольку 1 ≤ K ≤ N, таких случаев N ´ D(N - 1). Например, при N+1=5 и K = 2 мы рассматриваем множество перестановок (S1, 5, S 3, S 4, 2), в которых в качестве S1, S 3, S 4 фигурируют элементы 1, 3, 4 и S1 ≠ 1, S3 ≠ 3, S4 ≠ 4.

2.  Элемент N+1 находится на месте K, а на месте N+1 находится элемент M, при этом M ≠ K. Тогда элементы 1, 2, …, M-1, M+1, …, N находятся не на своих местах, а элемент N+1 не должен быть на месте M. Поскольку 1 ≤ M ≤ N, таких случаев N ´ D(N). Например, при N+1 = 5 и M = 3 мы рассматриваем множество перестановок (S1, S 2, S 3, S 4, 3), в которых в качестве S1, S 2, S 3, S 4 фигурируют элементы 1, 2, 4, 5 и S1 ≠ 1, S2 ≠ 2, S3 ≠ 5, S4 ≠ 4.

Суммирование по обоим вариантам доказывает рекуррентную формулу (2). В соответствии с ней, например, D(5) = 44.

Можно получить более очевидное, но и более сложное по форме соотношение для D(N+1). Всего имеется (N+1)! перестановок из N+1 элементов. Число перестановок с единственным элементом на своем месте составляет CN+11 ´ D(N), с двумя на своих местах CN+12 ´ D(N-1) и т. д. Ровно N элементов на своих местах быть не может, так как и последний элемент в этом случае на своем месте. Вычитая из общего числа перестановок количество случаев, когда хотя бы один элемент находится на своем месте, получим формулу

D(N+1)= (N+1)! - CN+11 ´ D(N) - CN+12 ´ D(N-1) -…- CN+1N-1 ´ D(2) – 1

Единица соответствует случаю, когда все элементы на своих местах.

Примеры:

1)  N=4, K=1. Тогда S = CNK ´ D(N-K) = 4´2 = 8, PNK = 8 / 4! = 1 / 3

2)  N=4, K=2, S = 6´1 = 6, PNK = 6/24 = 1 / 4

3)  N=5, K=2, S = 10´2 = 20, PNK = 20 / 120 = 1 / 6 (пример из условия)

4)  N=6, K=2, S = 15´9 = 135, PNK = 135 / 6! = 135 / 720 = 3 / 16

5)  N=10, K=9, S = C109 ´ D(1) =10´0 = 0, PNK = 0

Для нахождения D(N-K) в формуле (1) будем использовать процедуры длинной арифметики. Каждое длинное число представим последовательностью байтов, содержащих его десятичные цифры от младших разрядов к старшим. Потребуются такие процедуры как преобразование короткого числа типа INTEGER в длинное, сложение длинных чисел, умножение короткого числа на длинное и т. п.

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

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

По заданным ограничениям все числа не превосходят 100100, поэтому для представления любого длинного числа потребуется не более 200 байтов.

Приведем текст программы. Процедуры и функции длинной арифметики используются без изменений, поэтому в тексте содержатся только их заголовки.

Program Mag;

Const

numlen = 200; {число разрядов длинного числа - с запасом}

Label

Konec;

Type

number=array[1..numlen] of byte;

Var

M, N,K, L,i, j,jj : integer;

Min, Max: integer;

d1,d2,d3: number;

Num: array[1..100] of integer;

{кратность сомножителей знаменателя}

Fin, Fout: text;

Procedure Set0(var n:number); {обнуление длинного числа}

Procedure SetN(Var n: number; short: integer);

{занесение короткого числа в длинное}

Function Len(var n:number): integer;

{получение длины числа, для нуля длина 1}

Procedure Show(var n:number);

{вывод числа в файл Fout}

Procedure MulShort(Var n: number; short: integer);

{умножение длинного числа на короткое}

Procedure DivShort(Var n: number; divisor: integer;

Var rem: integer);

{деление длинного числа на короткое и получение остатка}

Procedure Add(Var n1,n2: number);

{сложение длинных чисел}

Procedure Move(n1:number; Var n2:number);

{пересылка длинного числа - n2:=n1}

Begin {основная программа}

Assign(Fin,'input. txt');

Reset(Fin);

ReadLn(Fin, K,N);

Close(Fin);

Set0(d1); { d1:=0 }

SetN(d2,1); { d2:=1 }

L:=N-K;

Assign(Fout,'output. txt');

Rewrite(Fout);

if L=1 then

begin

WriteLn(Fout,'0');

Goto Konec;

end;

{нахождение числителя d3}

if (L=0) or (L=2) then SetN(d3,1); { d3:=1 }

For i:=3 to L do

begin

Add(d1,d2); { d1:=d1+d2 }

Move(d1,d3); { d3:=d1 }

MulShort(d3,i-1);

Move(d2,d1); { d1:=d2 }

Move(d3,d2); { d2:=d3 - следующий шаг }

end;

if L<K then

begin

Min:=L;

Max:=K;

end

else

begin

Min:=K;

Max:=L;

end;

For i:=1 to Min do Num[i]:=2;

{кратность сомножителей знаменателя,

в K! и (N-K)! начальные сомножители повторяются}

For i:=Min+1 to Max do Num[i]:=1;

For i:=Max downto 2 do {проверка: можно ли сократить на i}

begin

jj:=Num[i]; {сомножитель i в знаменателе N[i] раз}

For j:=1 to jj do

begin

Move(d3,d1); {d1:=d3}

DivShort(d1,i, M); {M-остаток}

if M=0 then

begin

Num[i]:=Num[i]-1;

Move(d1,d3); {сокращение на i}

end

else break; {нет сокращения - выход из цикла по j}

end;

end;

SetN(d2,1);

{нахождение знаменателя d2 после сокращения}

For i:=2 to Max do

For j:=1 to Num[i] do

MulShort(d2,i);

Show(d3); {вывод в файл d3}

Write(Fout,'/');

Show(d2);

Konec:

Close(Fout);

End.

Необходимые для решения задачи процедуры и функции длинной арифметики используются без какого-либо изменения и настройки. В качестве упражнений можно порекомендовать довести до конца при максимальных размерностях решение приведенных выше задач, которые требуют применения длинной арифметики. Полезно также переработать процедуры длинной арифметики на язык Си и протестировать их на небольших комбинаторных задачах.