            Системы счисления и арифметические задачи.

                            Задача 1.
     Если вспомнить,  что  признаком деления на 9 в десятичной
системе счисления является делимость на  9  суммы  цифр  числа
(действительно, пусть есть число
 S = a[n]*10^n + a[n-1]*10^(n-1) + ... + a[1]*10 + a[0].
 S mod 9 = (a[n]*(10^n-1)+a[n] + a[n-1]*(10^(n-1)-1)+a[n-1] +
            + ... + a[1]*(10-1)+a[1] + a[0]) mod 9
     А так как 10^k - 1 делится на 9 нацело, то и
          S mod 9 = (a[n] + ... +a[1] +a[0]) mod 9,
ч.т.д.), то аналогично получаем, что признаком деления на 15 в
системе счисления с базисом 16 будет  делимость  на  15  суммы
всех шестнадцатеричных цифр числа.
     Мы разбиваем двоичное число справа налево на тетрады, ко-
торые  однозначно можно преобразовать в шестнадцатеричные циф-
ры, находим их сумму и делим ее на 15. Если остаток 0, то вве-
денное число делится на 15, иначе - нет.

                          Задача 2.
     Разумеется, можно  непосредственно  вычислить это число в
десятичной системе счисления,  после чего разделить его на  m,
но в этом случае придется представлять число в виде (например)
массива цифр и моделировать операции над этим числом.  Сущест-
вует другой простой алгоритм.
     В системе счисления с основанием K число представляется в
виде
     a[n]*K^n + a[n-1]*K^(n-1) + ... +a[0]*K^0.
     Найдем остаток  от деления его на m (остаток от деления a
на b обозначим a mod b):
   (a[n]*K^n +  a[n-1]*K^(n-1)  +  ...  +a[0]*K^0) mod m =

   ┌  n          ┐         ┌  n                   ┐
  =│ SUM a[i]*K^i│ mod m = │ SUM a[i]* (K^i mod m)│ mod m =
   └ i=0         ┘         └ i=0                  ┘

     Это следует из следующих соображений:  пусть K^i mod m=t,
тогда K^i =p*m+t, и
 (a[i]*K^i) mod m = (a[i] * (p*m+t)) mod m =
       = (a[i]* p*m) mod m + (a[i]*t) mod m =
       = (a[i] * (K^i mod m)) mod m,
при этом для любых чисел b[i] выполняется
    n                   n
 ( SUM b[i] ) mod m =( SUM b[i]  mod m ) mod m.
   i=0                 i=0

     Отметим также очевидное равенство
     K^i mod m =[(K^(i-1) mod m) * K] mod m,
т.к. если K^(i-1) = p*m+t, то K^(i-1) mod m = t,
K^i = p*m*K+t*K и K^i mod m = t*K mod m =
    = [(K^(i-1) mod m)*K] mod m.
   Запись этого алгоритма (тут a[i] - K-ичные цифры числа):
      s:=0;  t:=1;
      for i:=0 to n do
        begin
          s:=(s+a[i]*t) mod m;
          t:=t*K mod m;
        end;
     В переменной S после  окончания  работы  алгоритма  будет
храниться искомый остаток.

                          Задача 3.
     Задача решается также, как и предыдущая:
         ┌   s                                ┐
N mod K =│  SUM  (d[j] mod K) * ((s+1)! mod K)│ mod K,
         └  j=0                               ┘

                   ┌                           ┐
где (s+1)! mod K = │ (s! mod k) * ((s+1) mod k)│ mod k,
                   └                           ┘
    Алгоритм запишется следующим образом:

       остаток:=0;
       faktorial:=1;
       for i:=1 to s+1 do
         begin
           остаток:=(остаток+(d[i-1] mod k)*faktorial) mod k;
           faktorial:=(faktorial * ((i+1) mod k)) mod k;
         end;

    В переменной  остаток после выхода из цикла будет искомое зна-
чение.

                            Задача 4.
     Воспользуйтесь тем, что
                       U[1] + U[1] = U[2],                    (1)
     U[i] + U[i] = U[i] + U[i-1] + U[i-2] = U[1+1] + U[i-2],  (2)
                     U[i] + U[i-1] = U[i+1].                  (3)
     Суммируем числа A и B поразрядно,  используя приведенные выше
правила, начиная со старших разрядов.  После применения любого  из
правил опять начинаем просмотр числа со старших разрядов.
     Проведем суммирование чисел '10101' и  '100' из задачи.
     10101
  +    100
    -------
     10       Первые два разряда просто сносятся,
  +   1001    затем применяем правило (2),
  +     01    и добавляем последние два разряда
  +     00    чисел A и B
    -------
     11001    Для двух первых разрядов применяем правило (3)
  +     01
  +     00
    -------
    100001
  +     01    Правило (1)
  +     00
    ------
    100010

                            Задача 5.
     Алгоритм следующий:

   cnt:=0;               cnt -- счетчик единиц в i.
   while (i<>0) do       цикл повторяется число раз, равное
     begin               числу единиц в i. " Убираем " край-
       i:=(i-1) and i;   нюю справа единицу в двоичной записи
       cnt:=cnt+1;       числа.
     end;                Пример:  110  = i
                                  101  = i-1
                                  ------------------
                                  100  = i and (i-1)


                           Задача 6.
     Пусть a(k) - k-ый член последовательности.
     Рассмотрим последовательность, формируемую по следующему пра-
вилу:
                             a(0)=0;
ряд
                         a(0)...a(2**k-1)
получаем приписыванием  к  этой  последовательности справа этой же
последовательности, но при этом каждый  член  приписываемой  части
увеличивается на единицу. Получаем
                    0->01->0112->01121223->...
     Докажем, что a(k) есть сумма единиц в двоичном  представлении
числа k.
     Доказательство проведем по индукции.  Для a(0)=0 это справед-
ливо.    Пусть    предположение   справедливо   для   всех   a(i),
0<=i<=2^(k-1)-1 (т.е.  для всех чисел i, состоящих из не более чем
k-1-го  двоичных  разрядов).  Тогда в двоичном разложении числа l,
2^(k-1)<=l<2^k,  в k-ом разряде появляется добавочная  единица,  и
поэтому
                    a(l)=1+a(l-2^(k-1)),
ч.т.д.
     Возьмем a(i) mod 3,  и получим число, стоящее на i-ом месте в
последовательности, описанной в условии задачи.
     Для того,  чтобы найти a(i), необходимо, по доказанному,сосчи-
тать количество единиц в двоичной записи числа i - см. задачу 5.

                           Задача 7.
     Будем менять местами содержимое переменных A и B. Сущест-
вует несколько способов сделать это.
     1.  Оператор        Значение в A        Значение в B

         A:=A+B;             A+B                   B
         B:=A-B;             A+B                   A
         A:=A-B;              B                    A
     2. Можно  использовать логическую операцию XOR (исключаю-
щее или). Таблица истинности для XOR следующая:
         1 XOR 1 = 0               1 XOR 0 = 1
         0 XOR 0 = 0               0 XOR 1 = 1
     Операция XOR  над  двумя переменными в машине реализуется
как побитовая операция над двоичным представлением чисел. Поэ-
тому, в частности, A XOR A = 0, A XOR B = B XOR A, A XOR 0 = A.

         Оператор        Значение в A        Значение в B

        A:=A XOR B         A XOR B                 B
        B:=A XOR B         A XOR B           (A XOR B) XOR B=
                                             =A XOR (B XOR B)=
                                             =A XOR 0 = A
        A:=A XOR B       (A XOR B) XOR A=          A
                        = B XOR (A XOR A)=
                           = B

                            Задача 8.
     Если рассмотреть битовые представления числа A[i,j],  по-
мечающего точку  (i,j) и чисел i и j,  то обнаруживается,  что
A[i,j]=i XOR j,  откуда получается, что A[i,j] XOR i=j,
A[i,j] XOR j=i.
     Покажем, что A[i,j]=i XOR j.
     1) Число A[i,j]=i XOR j не встречалось еще ни в строке i,
ни в столбце j. От противного: существует такое j', что
     i XOR j = i XOR j' =>  i XOR j XOR i = i XOR j' XOR i  =>
     =>  j'=j;
     2) Пусть  существует  такое k<i XOR j,  что k=i XOR L =
= j XOR M,  и k еще не встречалось в строке i и столбце j (на-
помним, что  по  предположению  все  остальные уже заполненные
элементы равны i XOR j, поэтому L>j и M>i).
     Тогда, так как M>i,  то существует бит с номером t такой,
что для любого R>t биты Mr и ir равны, t-ый бит Mt=1, it=0. Но
так как j XOR M < j XOR i, то Jt=1.
     Так как L>j и L XOR i=j XOR M,  то L = j  XOR  M  XOR  i.
Рассмотрим i  XOR  M.  В силу вышесказанного для любого бита с
номером R, R>t, (i XOR M)r=0, а (i XOR M)t=1.
     При этом Jt=1, следовательно
     (i XOR j XOR M)r = Jr для r>t и
     (i XOR j XOR M)t = 0  для r=t,
то есть L<j ?! Противоречие.

                            Задача 9.
     Введем переменную N1=N.
     Пусть N1 и M заданы в десятичной системе счисления. Пере-
ведем дробь N1/M в систему счисления с основанием p:
     Пусть в системе с основанием p искомая дробь 0.a(1)a(2)...
     Получаем:
     a(1)*p^(-1)+a(2)*p^(-2)+ ... =N1/M.
Умножим правую и левую части равенства на p:
     a(1)+a(2)*p^(-1)+ ... = N1*p/M.
     Выделяя целую часть выражений слева и справа от знака ра-
венства, получаем
     a(1) = целая часть (N1*p/M).
Обозначим N2 = N1*p mod M; очевидным образом получаем
     a(2)*p^(-1)+ ... = N2/M.
Домножая на p и находя целую часть, опять же имеем
     a(2) = целая часть (N2*p/M);
продолжая аналогично, определяем коэффициенты a(3), a(4) и т.д.
     В ходе выделения цифр ai мы можем получить различных зна-
чений Ni не более чем M (по алгоритму выше у нас всегда Ni<M).
     Если вдруг какие-то два остатка совпадают:  Ni=Nj,  i<>j,
то совпадают и цифры разложения: a(i+1)=a(j+1), a(i+2)=a(j+2),
... ,  т.е. цифры (a(i+1), ... ,a(j)) образуют один из кратных
периодов. Нам  надо найти минимальную длину такой периодически
повторяющейся последовательности,  которая  равна   количеству
цифр между двумя ближайшими повторяющимися остатками,  и  сами
цифры.
     Поступаем следующим образом:
Выделяем M  цифр  p-ичной  дроби (исходя из вышесказанного,  к
этому моменту период уже обязан начаться).  Запоминаем  Nm,  и
ищем первый такой остаток Nk, k>m, что Nm=Nk. Величина k-m как
раз и есть искомая длина периода.

                         Задача 9.1.
     Алгоритм:
     p:=0; q:=1;
     metka:
         if p/q < r then p:=p+1;
         if p/q = r then stop;
         if p/q > r then q:=q+1;
         if q > qmax then stop;
         goto metka;

PROGRAM  ratap;
VAR  p,q,qmax:integer;
     d, r, min: real;
BEGIN
   write('r,qmax=');  readln(r,qmax);
   p:=0; q:=1; min:=r;
  REPEAT
    IF  p/q<r THEN p:=p+1 ELSE q:=q+1;
    d:=abs(r-p/q);
    IF d<min THEN BEGIN min:=d; writeln(p:7,'/',q) END
  UNTIL (q>=qmax) OR (d=0);
readln; END.

     Задача взята из книги "Еxploring mathematics with your
computer" by Arthur Engel (The Mathematical Association of
America, New Mathematical Library, 1993)



                          Задача 10.
     Так как q<p, то цифры a и b должны лежать в пределах от 0
до q-1.
     Распишем A в системе с основанием p:

         a    b     a     b            1            1
     A = - + ─── + ─── + ─── + ...  = ─── (ap+b) + ─── (ap+b)+
         p   p^2   p^3   p^4          p^2          p^4

+ ... = (ap+b)(p^(-2) + p^(-4) + ...) =  { находим  сумму  бесконечно
убывающей  геометрической прогрессии со знаменателем p^(-2)} =
          p^(-2)    ap+b
 = (ap+b)─────── = ───── .
         1-p^(-2)   p^2-1
     Аналогично для A в системе с основанием q выполняется
         bq+a
     A = ───── .
         q^2-1
     Получаем
                 (bq+a)(p^2-1)=(ap+b)(q^2-1)
           a[p(q^2-1)-(p^2-1)]=b[q(p^2-1)-(q^2-1)].
     Вычисляем выражения  в  квадратных скобках;  обозначим их
соответственно u и v: au=bv.
     Находим НОД(u,v)=s; обозначим r=u/s, f=v/s.
     Получаем
           ar=bf,
r и f взаимно просты, следовательно, решениями этого равенства
будут числа
     a=fk, b=rk, k=1,2, ... ,
     при этом  мы берем только те a и b,  для которых одновре-
менно выполняется
     а) a<>b
     b) a<r
     c) b<r
     Нахождение НОД - см. задачу 12.

                            Задача 11.
    Очевидное решение: При попытке непосредственно вычислять коор-
динаты концов сегментов,  принадлежащих множеству K[n],  и опреде-
лить,  принадлежит  ли  a/b  одному  из этих сегментов даже для не
слишком больших n за счет потери точности при вычислениях и  из-за
ограниченного числа знаков в машинном представлении чисел с плава-
ющей точкой данный подход  дает  неверный  ответ  для  большинства
входных данных. При больших n вообще будет наблюдаться потеря зна-
чимости:  число при делении на 3 станет таким малым,  что в машине
оно будет представляться нулем.
    Рассмотрим другой метод решения этой задачи. Так как мы посто-
янно  должны  делить сегменты на три части,  то это наталкивает на
мысль использовать троичную систему счисления и троичные дроби.
   В первой из удаленных интервалов (1/3,2/3) попадают только
те точки
                 x=0.a[1] a[2] a[3] ...
в троичном разложении которых a[1]=1, кроме точки 1/3=0.1000... --
правого конца  сегмента [0,1/3].  Таким образом,  в K [1] остаются
все те точки,  у которых a[1] <>1,  либо a[1]=1, a[2] = a[3] = ...=
= 0. Аналогично, в множестве K[i], i>=0, содержатся точки, у кото-
рых ни одно из чисел a[j],  1<=j<=i,  не равно 1,  а также  точки,
удовлетворяющие   условию:   a[j]=1,  j  -  фиксировано,  1<=j<=i,
a[l]<>1, l<j, и a[l] =0 для любого l>j (то есть, в записи троичной
дроби только одна позиция равна 1, после нее все остальные позиции
нулевые.  Эти дроби соответствуют правым концам сегментов из  мно-
жества K[i]).
    Запись алгоритма на Паскале имеет вид:
      x:=a;  i:=1;
      while (i<=n) or (x<>1) or (a<>0) do
         begin
            a:=a*3 mod b;
            x:=a*3 div b;
            i:=i+1;
         end;
      if (x=1) and (a<>0) and (n<>0)
         then writeln(' Не принадлежит')
         else writeln(' Принадлежит');

                            Задача 12.
     Как известно НОК(a,b)=ab/НОД(a,b).
     Для нахождения НОД используем алгоритм Евклида. Будем обозна-
чать НОД(a,b) просто как (a,b).
     Шаг алгоритма. Пусть a>=b (если это не так, то просто поменя-
ем содержимое переменных a и b местами).
     Если b=0, то (a,b)=a, СТОП.
     Иначе (a,b)=(a mod b,b).
     Действительно, если g=(a,b),  то он делит и a, и b, и остаток
r от деления a на b: a=bs+r, тут s - частное a div b, r = a mod b.
Покажите, что (a,b)=(r,b).
     Обозначим через a величину a mod b.  Снова выполним шаг алго-
ритма.

     Существует и  другой,  более быстрый ('машинный') вариант на-
хождения НОД:
     Для вычисления  НОД  воспользуемся  следующими очевидными ра-
венствами:
     1). (0,a)=a, (a,b)=(b,a)
     2). (a,b)=(a-b,b)
     3). Если a и b оба четны, то (a,b)=2*(a/2,b/2)
     4). Если a четно,  а b - нет, то (a,b)=(a/2,b)
     5). Если  a  и b оба нечетны и a>b,  то (a-b) - четное число,
при этом (a-b)<max{a,b} и (a,b)=(a-b,b).
     Алгоритм :
     Шаг 1.     k:=1
     Шаг 2.     Пока a и b одновременно четны, выполняем
                        a:=a/2
                        b:=b/2
                        k:=k*2
     Шаг 3.  Если оба числа a и b нечетны,
             то на место большего из них заносим разность его и
                        меньшего из чисел,
             иначе,
               если одно из чисел a или b четно,
               то делим его на 2.
     Шаг 4.  Если одно из чисел (a или b) равно нулю,
             то (a,b) равен произведению другого числа на k, и ал-
                горитм завершает работу,
             иначе перейти на шаг 3.

                            Задача 13.
                 p-1    p
     Число вида 2   * (2 - 1), в двоичном представлении имеет р
единиц и р-1 нулей. Максимальное значение р определяется как
                  [(log N)/2]+1.
                       2
     Затем проверяется является ли число совершенным для  получен-
ного значения p.  Оно является совершенным, если для простого зна-
                 p
чения p,  число 2 -1 является простым. Если получили несовершенное
число,  уменьшаем  p  на  1 и снова проверяем,  является ли данное
число простым.
     Совершенные числа получаются для значений р равных
                2,3,5,7,13,17,19,31,61,89,107,127.

                            Задача 14.
     Запишем уравнение в виде
                     sXeAk + pY = nYmAt + rX.
     Приравнивая коэффициенты при X,A и Y, получаем:
 X │ se=k
 A │ p=nm                                                     (*)
 Y │ sk=nt
     Так как коэффициенты в формуле должны быть взаимно  простыми,
то следует найти НОД чисел k и t (Задача 12). Пусть (k,t)=d. Тогда
s*(k/d)=n*(t/d), и числа k/d и t/d являются взаимно простыми, сле-
довательно, n=k/d, а s=t/d.
     По (*) находим остальные коэффициенты.

                            Задача 15.
     По заданным координатам трех вершин мы  можем  найти  площадь
треугольника ABC
            Sabc=(bx-ay)/2
     Если a=0,  то  минимальная  площадь  Smin=b/2,  если b=0,  то
Smin=a/2.  Если же обе координаты отличны от нуля, то из алгоритма
Евклида для нахождения НОД(a,b)=(a,b), следует существование таких
целых x и y, что ABS(bx-ay)=(a,b), и именно эти x и y минимизируют
площадь треугольника ABC.
     Нахождение НОД - задача 12.

                            Задача 16.
     Обозначим S=НОД(V1,...,Vn).  Если V делится нацело на S, то в
сосуд с помощью банок можно налить V литров воды, иначе - нет.

                            Задача 17.
     Заведем два массива: E[0..N+1] и S[0..N+1]. Элементы массивов
- байты. В E будем хранить текущую частичную сумму
             e_n=1+1/1!+1/2!+ ...  +1/(k-1)!,                  (*)
вычисленную с точностью N+1 знаков после запятой  (в  ячейке  E[i]
хранится значение i-го разряда после запятой,  то есть коэффициент
при 10^(-i)).  В массиве S  будет  храниться  последнее  слагаемое
частичной суммы, т.е. 1/(k-1)! (опять же в S[i] находится i-я циф-
ра после запятой, все незначащие цифры, разумеется, нули).
     Оценим погрешность формулы (*) c учетом равенства
                e=1+1/1!+1/2!+ ...  +1/(k-1)!+...
Погрешность представления числа е будет
     F_n = e-e_n = 1/(n+1)! + 1/(n+2)!+ ...
         = 1/(n+1)! * (1 + 1/(n+2) + 1/(n+2)(n+3) + ...)
         < 1/(1+n)! * (1 + 1/(n+2) + 1/(n+2)^2 + ...)

             1          1            1     n+2
         = ──────  ───────────  =  ─────  ────
           (n+1)!  1-(n+2)^(-1)    (n+1)!  n+1

     Т.к. F_450 < 10^(-10002),  то для вычисления,  например, 1000
знаков после запятой необходимо 450 итераций.  По точности N и вы-
шеприведенной формуле вычисляем количество итераций С (можно взять
грубо С=N).
     Будем делить число,  представленное массивом S,  на очередное
число k. Результат 1/k! прибавим к массиву E. Сложение реализуется
так:
     perenos:=0;     { перенос из предыдущего разряда }
     for i:=N+1 downto 0 do
     begin
       E[i]:=E[i]+S[i]+perenos;
       perenos:=E[i] div 10;  { формируем новый перенос }
       E[i]:=E[i] mod 10;     { корректируем E[i] }
     end;
     Вычисление новых  слагаемых  и суммирование проводится С раз.
     Рассмотрим процедуру  деления S на k.  Делить будем так,  как
это обычно делается вручную - "столбиком":
     m:=0;    { m - текущее делимое, m - Longint }
     for i:=0 to N+1 do begin
       m:=m*10+a[i];  { дописываем к делимому сзади еще }
                      { одну цифру }
       a[i]:=m div k; { находим очередную цифру частного }
       m:=m mod k;    { и очередное делимое }
     end;

                            Задача 18.
     В переменной  стандартного  типа  такое  большое число не по-
местится.  Будем моделировать возведение  2  в  степень  n  вычисляя
последовательно 2^1,  2^2,  ...  , 2^n, используя массив. В каждой
ячейке массива будем хранить  по  (например)  4  десятичных  цифры
числа (т.е. в элементе A[1] - 4 последних цифры числа (разряды 0 -
3), в A[2] - 4 предпоследних (разряды 4 - 7) и т.д.).
     Оценим количество десятичных цифр в числе 2^n,  n<=1000.  Это
10 000 * log10 (2) + 1 < 15 000 цифр. Количество элементов массива
возьмем равным 15000/4=3750. Введем переменную Nach, в которой бу-
дем хранить индекс элемента массива A, в котором находятся старшие
значащие разряды вычисляемого сейчас числа.
     var A: array[1 .. 3750] of word;
         Nach: word;
         i,N,j: word;
     begin
       for i:=2 to 3750 do A[i]:=0;
       A[1]:=1;   { сначала число в массиве A - это 2^0=1 }
       read(N);   { читаем степень }
       Nach:=2;   { индекс первой еще не использованной ячейки }
                  { в массиве A }
       for i:=1 to N do
       begin
         Perenos:=0; { перенос в следующий элемент массива A }
         for j:=1 to Nach+1 do
         begin
           A[i]:=A[i]+A[i]+Perenos;
               { складываем 4 текущих разряда друг с другом, }
               { добавляя перенос из предыдущих 4-х разрядов }
           if A[i]>=10000        { если в числе > 4 цифр }
           then begin
             Perenos:=A[i] div 10000;  {то формируем перенос}
                                       { в старшие разряды }
             A[i]:=A[i] mod 10000;     { и оставляем в числе }
                                       { 4 последних цифры }
           end
           else Perenos:=0       { иначе переноса нет }
         end;   { к вложенному циклу for j }
         if A[Nach+1]>0          { если был перенос в еще не }
         then Nach:=Nach+1;      { использованную ячейку }
                            { массива A, то увеличиваем Nach }
       end;   { для цикла for i }
           { распечатка }
       { старшая тетрада печатается без ведущих нулей }
       j:=1000;           { ищем первую значащую цифру }
       while (A[Nach] div j)=0 do j:=j div 10;
       while j<>0 do begin
         write(A[Nach] div j);    { печать цифры }
         A[Nach]:=A[Nach] mod j;  { отбрасываем }
         j:=j div 10;             { напечатанную цифру }
       end;
       for i:=Nach-1 downto 1 do
       begin
         j:=1000;
         for j:=1 to 4 do    { 4 разряда }
         begin
           write(A[i] div j);  { печатаем цифру }
           A[i]:=A[i] mod j;   { и отбрасывает ее }
           j:=j div 10;
         end
       end
     end. { программы }

                            Задача 19.
     Решается, аналогично задаче 18, моделированием вычисления
N^1, N^2, ... , N^N.

                            Задача 20.
     Можно просто каждое число S, 1<S<=N, делить на все предыдущие
натуральные числа k,  1<k<S,  и если хоть один остаток от  деления
равен нулю, то S - не простое. Пусть S - составное, S=ab, при этом
обязательно a<=SQRT(S), а b>=SQRT(S), так что для проверки просто-
ты S имеет смысл проверять не все значения делителя k от 2 до S, а
только k не превосходящее SQRT(S).  Если число S -  составное,  то
его можно разложить в произведение простых чисел, поэтому, так как
мы уже нашли все простые числа меньшие S,  то S имеет смысл делить
только на простые числа,  не превосходящие SQRT(S).  Если S>2,  то
следует рассматривать только нечетные числа.
     Алгоритм.
     Пусть A  -  упорядоченное  по  возрастанию  множество простых
чисел, сначала A={2,3}.
     Пусть N>3.
     Для S от 5 до N с шагом 2 повторять
       Для всякого простого числа x<=SQRT(S) повторять
         если остаток от деления S на x не равен нулю,
         то S - простое,  добавляем S в A
         иначе S - составное.

                            Задача 21.
      Мы можем представить N! в виде произведения простых сомножи-
телей:
               N!=(2^A2)*(3^A3)*(5^A5)*(7^A7)*...,
где Ap  -  показатель степени,  с которой простое число р входит в
разложение. Видно, что нулей в конце числа столько же, сколько ну-
лей в  конце произведения (2^A2)*(5^A5), но так как, очевидно, что
A2>A5, то количество нулей равно A5.
   Для того, чтобы найти A5, необходимо вычислить сумму

            ┌  N  ┐   ┌  N  ┐   ┌  N  ┐
         A5=│ ─── │ + │ ─── │ + │ ─── │ +                      (*)
            └ 5^1 ┘   └ 5^2 ┘   └ 5^3 ┘  ... ,
           ┌   ┐
       где │   │ -- целая часть числа,
           └   ┘
т.к. каждое  пятое  число в произведении N!  делится на 5,  каждое
двадцать пятое число еще раз делится на 5,  каждое 5^3 число,  еще
раз делится на 5, и т.д. То есть в (*) мы находим, сколько чисел в
произведении N!  делится на 5. Фрагмент программы выглядит следую-
щим образом :
                 k:=5;
                 s:=0;
          repeat
                 s:=s+N div k;
                 k:=k*5;
          until (k>N);
     После работы цикла в переменной S будет находиться A5.

                          Задача 22.
     Найдем простые множители числа P. Пусть это будут p1,...,
pk.  Для каждого множителя pi найдем число si - степень, с ко-
торой pi входит в разложение P на простые сомножители. Как и в
задаче  21 найдем максимальные числа m1, ..., mk, такие что N!
делится на pi в степени mi,  но не делится  на  pi  в  степени
mi+1.
     Получаем для нахождения m следующее уравнение:
      N!    (p1^m1)*(p2^m2)*...*(pk^mk)*R
     ─── = ─────────────────────────────── ,
     P^m   ((p1^s1)*(p2^s2)*...*(pk^sk))^M
где R=N!/[(p1^m1)*(p2^m2)*...*(pk^mk)].
     Минимальное из чисел mi div si и даст искомую степень M.
     Рассмотрим пример: N=15, P=135.
     P=3*3*3*5, p1=3, s1=3, m1=15 div 3 + 15 div (3*3)=6
                p2=5, s2=1, m2=3.
     Получаем, что M=min{6 div 3, 3 div 1}=2.
     Объясните, почему мы не можем применить формулу
       M=N div P + N div (P**2) + N div (P**3) + ... ?

     Приведем полностью программу, реализующую этот алгоритм.

{                      Условие задачи.
     На входе программе даются два числа N и P.  Программа  на
выходе должна дать такое максимальное число M,  что N! делится
на P в степени M, но не делится на P в степени M+1.
    Примечание.
1. Числа N и P так велики, что нет смысла считать значение N!.
2. Числа N и P являются натуральными.
}

uses crt;
const
 max_long = 2147483647;
var
 n,p,i,stp,m,mn,km   : longint;
 flag                : boolean;
 ch                  : char;

{ Функция  howmany  считает,  сколько  раз  в  разложении числа n!
                    присутствует множитель mn.
}

function howmany(mn,n:longint):longint;
var
 pr1,pr2,pr3 : longint;
begin
 pr1:=mn; pr2:=0; pr3:=1;
 while pr3<>0 do
  begin
   pr3:=trunc(n/pr1);
   pr1:=pr1*mn;
   pr2:=pr2+pr3
  end;
 howmany:=pr2
end;

{  Функция st  находит  степень  множителя mn в разложении числа p
                      на простые множители.
}

function st(mn:longint; var n:longint):longint;
var
 prom: longint;
begin
 prom:=0;
 while (n mod mn)=0 do
  begin
   inc(prom);
   n:=n div mn
  end;
 st:=prom
end;

begin
 clrscr;
 while true do
  begin
   write('Введите число N и P => '); read(n,p);   { ввод }
   if p<>1 then                                   { если p=1 то число m }
    begin                                         { не существует       }
     m:=max_long;
     i:=2;
     flag:=true;
     repeat
       stp:=st(i,p);           {  stp после присваивания будет равно числу  }
       if (stp<>0) then        { вхождений множителя i в разложении числа p }
        begin                  { на простые множители.  Если  stp<>0, то km }
                               { будет равно  числу вхождений  множителя  i }
         km:=howmany(i,n);     { в разложении числа n! на простые множители }

         if (trunc(km/stp)<m) then  { если km/stp меньше минимального отно- }
          begin                     { шения, то сохраняем это значение.     }
           m:=trunc(km/stp);
           if m=0 then flag:=false
          end;
        end;
       if i=2 then i:=3 else inc(i,2);
     until (i>p) or (not flag);
     writeln('Число M равно ',m)
    end
    else
     writeln('Число M не существует.');
   write('Продолжить ? (y/n) ');
   repeat
    while keypressed do ch:=readkey;
    ch:=readkey;
    case ch of
     'Y','y': writeln('y');
     'N','n': begin writeln('n'); exit end
    end;
   until ch in ['N','n','Y','y'];
 end;
end.

{                            Описание задачи.
   Если взять два любых натуральных числа a и b, то a будет делиться на b,
если все степени множителей при разложении числа  a  на  простые множители
больше либо равны аналогичных степеней, получаемых при разложении числа b.

 Пример :
  120 = 2*2*2 * 3 * 5
  40  = 2*2*2 *     5
  120 делится на 40

   Следовательно, n! делится на p в степени m, если степень любого прос-
того число mn (2<=mn<=p)  в  разложении  числа  n!  на простые множители
больше, чем в аналогичном разложении числа p в степени m.
   Если F(i,p) - степень простого числа i в разложении  числа p на прос-
тые множители, то F(i,p^m)=F(i,p)*m.
   Отсюда алгоритм решения :
степень  m  будет  равна  целой  части от минимального отношения степени
простого числа i в разложении n! к степени числа i в разложении числа p,
где 2<=i<=p.
   Алгоритм разложения числа р на простые множители достаточно прост.
Основную трудность представляет алгоритм разложения числа n!.

алгоритм степень_простого_числа_в_разложении_числа_n! (нат n,mn,s,k)
дано n,mn
надо s
нач
 s:=0
 k:=mn
 пока [n/k]>0
  нц
   s:=s+[n/k]
   k:=k*mn
  кц
кон.

                            Задача 23.
     Воспользуемся тем,   что  для  n>=4  выполняется  неравенство
n<=(n-2)*2, т.е. разбивать число на слагаемые, большие 3, не имеет
смысла.  Выделяем из числа n слагаемые-двойки, пока не получим ос-
таток меньший либо равный 3 (остаток может быть либо 3,  либо  2).
Так как 2*2*2<3*3, то заменим каждые три двойки на две тройки. По-
лученное разложение и является искомым.
     Разберите самостоятельно случаи
     1) когда необходимо максимизировать произведение, и слагаемые
в  разложении числа n должны принадлежать промежутку [A,B],  A и B
вводятся пользователем.
     2) когда необходимо минимизировать произведение,  и слагаемые
в разложении числа n должны принадлежать промежутку [A,B],  A и  B
вводятся пользователем.

                            Задача 24.
     Если S>=4 то существуют единственные S1 и S2,  такие что
                        S=S1*S2=S1+S2.
Более того, наименьшее из S1 и S2 больше 1 и <=2:
        S1=(S-SQRT(S^2-4S))/2, S2=(S+SQRT(S^2-4S))/2,
              (S-4)^2=S^2-8S+16<=S^2-4S<(S-2)^2
и
                 1<S1=(S-SQRT(S^2-4S))/2<=2.
Итак, если r<4 то разложение  на  множители  закончено,  иначе
проводим разложение r на два множителя, один из них <=2 (и тем
более <4 ), если другой <4 , то процесс закончен, иначе повто-
ряем факторизацию S до тех пор, пока не получим искомое разло-
жение.

                            Задача 25.
     Из теоремы Виета получаем, что
     x1*x2*x3*x4*x5=-A(0)/A(5)
откуда следует,  что число xi должно быть делителем A(0)/A(5). На-
ходим все делители A(0)/A(5)=R (Если A(0)=A(1)=...=A(i)=0,  то i+1
корень  уравнения равен 0.  Мы делим уравнение на x^(i+1),  дальше
ищем делители числа r=A(i+1)/A(5)).
     i:=1;
     пока i<=R повторять
         если R делится нацело на i
         то проверить, являются ли числа +i
                      и -i корнями полинома
         i:=i+1
     конец пока

                            Задача 26.
     Пусть m/n  - текущая несократимая дробь.  Покажем,  как найти
следующую по значению дробь. Понятно, что она будет среди несокра-
тимых дробей вида k/р,  где р может принимать значения от 2 до 15.
Учитывая условие k/р > m/n можно для каждого р прямо вычислять ми-
нимальное значение k следующим образом:
            k=m*p/n+1.
     При этом каждая дробь k/р, полученная описанным выше образом,
несократима.
         m:=0; n:=1
         Повторять
          i:=1; j:=1;
          для р:=2 до 15 выполнять
           нц
            k:=m*p div n + 1;
            если k*j < p*i
                  то  i:=k; j:=p;
            все
           кц
          m:=i;  n:=j;
        пока i>=j


                            Задача 27.
     Это условие - равенство нулю суммы всех чисел.  Мы всегда мо-
жем "перетащить" с помощью последовательности ходов все  ненулевые
числа,  помечающие вершины,  в одну какую-либо вершину. Если сумма
всех чисел равна 0, то после этих ходов окажется, что во всех вер-
шинах записан 0.

                            Задача 28.
     а). Программа вычисления следующая:
     P:=a[N]
     for i:=N-1 downto 0 do
       P:=P*x+a[i];
     Посмотрите, как  эта  схема работает,  вручную найдя значение
полинома по его коэффициентам и точке x.
     b). Решается аналогично.

                            Задача 29.
     Продемонстрируем метод нахождения коэффициентов  полинома
на примере возведения p(x)=(x**2+2*x+1) в четвертую степень.
     Будем последовательно возводить полином в степени  2,  3,
4. Для второй степени справедливо равенство
     p(x)*p(x)=(x^2+2x+1)*(x^2+2x+1)=(x^2+2x+1)*x^2+
     +(x^2+2x+1)*2x+(x^2+2x+1)*1
     Будем складывать коэффициенты у  одинаковых  степеней  x,
выписывая коэффициенты полинома первой степени с соответствую-
щим сдвигом и умножаем на коэффициент:
     x^4   x^3   x^2   x^1   x^0
   ───────────────────────────────────┐
                  1     2     1       │   x^2+2x+1
            2     4     2             │   (x^2+2x+1)*2x
      1     2     1                   │   (x^2+2x+1)*x^2
   ───────────────────────────────────┘
      1     4     6     4     1
     Получили коэффициенты второй степени полинома. Для треть-
ей степени, поступая аналогично, получаем такую таблицу:
     x^6   x^5   x^4   x^3   x^2   x^1   x^0
    ──────────────────────────────────────────┐
                  1     4     6     4     1   │ p(x)*p(x)
            2     8    12     8     2         │ 2x*p(x)*p(x)
      1     4     6     4     1               │ x^2*p(x)*p(x)
    ──────────────────────────────────────────┘
      1     6    15    20    15     6     1
     Коэффициенты 4-ой степени:
     x^8  x^7  x^6  x^5  x^4  x^3  x^2  x^1  x^0
    ──────────────────────────────────────────────┐
                1    6   15   20   15    6    1   │
           2   12   30   40   30   12    2        │
      1    6   15   20   15    6    1             │
    ──────────────────────────────────────────────┘
      1    8   28   56   70   56   28    8    1
     С произвольным полиномом поступаем так же: последователь-
но находим степени 2,3,  ...,  m.  Когда мы знаем коэффициенты
полинома в  степени i,  то вычисляем коэффициенты степени i+1,
выписывая со сдвигом коэффициенты полинома степени i, умножен-
ные на соответствующие коэффициенты исходного полинома,  а за-
тем складываем их в столбик.

                            Задача 30.
     Решается аналогично предыдущей задаче. Рассмотрите полином
                  p(x)=(x-A[1])*...*(x-A[N])
и вычислите  его  коэффициенты.  На каждом из шагов,  в отличие от
предыдущей задачи, умножение будет производиться на новый одночлен
(x-A[i]).

                            Задача 31.
     Рассмотрим следующую задачу:
     Разделить полином  p(x)=a[n]*x^n  +  ...  +  a[1]*x+a[0]   на
v(x)=(x-d), т.е. найти такую константу - остаток r и такое частное
s(x)=s[n-1]*x^(n-1)+ ... + s[1]*x+s[0], что
                       p(x)=s(x)v(x)+r.
     Делить будем в столбик. Рассмотрим операцию деления полиномов
на примере:
     3x^2+2x+5 │x-2
     3x^2-6x   └────     Тут r=21, s(x)=3x+8.
     ───────    3x+8     Видно, что коэффициент s[n-1]  при
          8x+5           старшей степени x в s равен  коэф-
          8x-16          фициенту при старшей степени  x  в
          ─────          p, а остальные  коэффициенты  в  s
             21          находятся по формулам:


                    s[t-1]=(-d)*s[t]+p[t];
                      r=(-d)*s[0]+p[0].
     В наглядной  форме  это  можно записать в виде так называемой
схемы Горнера:
       p[n]         p[n-1]    ...        p[1]        p[0]
     ┌────────────────────────────────────────────────────────
 -d  │s[n-1]=p[n]           ...   s[0]=-d*s[1]+p[1]
     │      s[n-2]=-d*s[n-1]+p[n-1]             r=-d*s[0]+p[0]

     Тогда проведенное выше деление можно записать в следующем ви-
де:
        3        2       5
     ┌───────────────┬─────┬─
   2 │  3        8   │ 21  │ <- остаток
     │               └─────┘

     Тут 3 сносится, 8=2*3+2, 21=2*8+5.
     Вернемся к исходной задаче. Приравняем полиномы:
     p0(x)=a[n]*x^n+a[n-1]*x^(n-1)+ ... +a[1]*x+a[0]=
          =b[n](x-d)^n+ ... +b[1]*(x-d)+b[0].
     Находим остаток от деления полиномов справа и слева от  знака
равенства на (x-d). Слева все слагаемые, кроме последнего, делятся
на (x-d) нацело. Поэтому
     p0(x)=(x-d)*p1(x)+b[0].
     Получаем, что
     p1(x)=b[n]*(x-d)^(n-1)+ ... +b[2]*(x-d)+b[1].
     Аналогично находим b[1]:
     p1(x)=(x-d)*p2(x)+b[1],
затем по p2(x) определяем b[2], и т.д., пока не найдем b[n].
     Особенно удобно  это записывается в виде схемы Горнера (обра-
тите внимание,  что в верхней строке записаны коэффициенты p0, то,
что получается в строке ниже - это коэффициенты p1, к которым так-
же можно применить схему Горнера, находя коэффициенты p2, и т.д.)
     Пример: p(x)=3x^2+2x+5, d=-2,
       3   2    5
    ┌─────────┬────┐
  2 │  3   8  │ 21 │ =b[0]
    │    ┌────┼────┘                14=2*3+8
  2 │  3 │ 14 │ =b[1]
    ├────┼────┘
  2 │  3 │ =b[2]
    └────┘
     Получаем
           3x^2+2x+5=3(x-2)^2+14(x-2)+21.

                            Задача 32.
     Пусть f(x)=ax^4+bx^3+cx^2+dx+e. Выразим f(x+1) через f(x):
f(x+1)=f(x)+(4ax^3+(6a+3b)x^2+(4a+3b+2c)x+(a+b+c+d)=f(x)+g(x),
где
     g(x)=Ax^3+Bx^2+Cx+D.
Поступим аналогично и с g(x):
     g(x+1)=g(x)+(3Ax^2+(3A+2B)x+(A+B+C))=g(x)+h(x), где
     h(x)=A'x^2+B'x+C'.
Далее:
     h(x+1)=h(x)+(2A'x+(A'+B'))=h(x)+p(x),
где
     p(x)=A"x+B". p(x+1)=p(x)+A".
Имеем:
        f(x+4)=f(x+3)+g(x+3)
        g(x+3)=g(x+2)+h(x+2)
        h(x+2)=h(x+1)+p(x+1)
        p(x+1)=p(x)+A".
Отсюда получаем фрагмент программы:
     < BLOCK 1 >
     x:=5;
     repeat
       P:=P+A2;
       H:=H+P;
       G:=G+H;
       F:=F+G;
       writeln(x,F);
       x:=x+1;
     until x=10001;

     Итак, на  каждое значение,  начиная с 5,  тратится 5 операций
сложения.  Остается около 1000 операций на вычисление f(1),  f(2),
f(3), f(4), для инициализации
     P:=p(1); H:=h(2);  G:=g(3); (F:=f(4));
и на вычисление  A2:=A". Ясно, что 1000 операций хватит на все эти
вычисления.

