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

                            Задача 1.
     Число вводится  своим двоичным представлением (длина числа не
превышает 10000 двоичных разрядов). Необходимо определить  делится
ли число на 15.

                            Задача 2.
     Дано число в K-ичной системе счисления
            a a   ...a   (K<=36).
             n n-1    0
Найти остаток от деления его на m.
     Числа K,  n, m, как и остаток от деления на m, представляются
в десятичной системе счисления.

                            Задача 3.
     Любое натуральное  число  N   можно   единственным   способом
представить  с  помощью некоторых целых неотрицательных d[0], ... ,
d[s] в виде
            N=d[s]*(s+1)!+d[s-1]*s! +...+d[1]*2!+d[0]           (*)
при условии, что 0<=d[i]<=i+1, i=0,..,s, где d[s]<>0.
     Дано s+1 натуральное число d[0],  ..., d[s], и натуральное K,
s<200,d[i]<65535, K<65535. Найти остаток от деления числа N, опре-
деляемого в факториальной системе (*) числами d[0],  ..., d[s], на
число K.

                            Задача 4.
     Числа Фибоначчи U[1],  U[2], ... определяются начальными зна-
чениями U[1]=1, U[2]=2 и соотношением
                     U[N+1] = U[N] + U[N-1].
     Рассмотрим систему счисления с двумя цифрами 0 и 1,  в  кото-
рой, в  отличие  от  двоичной  системы  весами являются не степени
двойки 1,2,4,8,16,...,  а числа Фибоначчи 1,2,3,5,8,13,.... В этой
системе счисления  каждое  положительное  целое число единственным
образом представляется в виде строки нулей и единиц, которая начи-
нается с 1 и в которой нет двух единиц, стоящих рядом.
     Даны две строки,  представляющие числа A и B.  Найти  строку,
представляющую число A+B.
     Пример. Исходные строки '10101' и  '100' представляют  числа
8+3+1=12 и  3.  Ответом  является строка '100010',  представляющая
строку 13+2=15=12+3.
     Примечание. Строки  могут быть столь длинны,  что числа A и B
превысят максимально допустимое в вашем компьютере целое число.

                            Задача 5.
     Сосчитать количество единиц в двоичной записи числа i.

                            Задача 6.
     Последовательность 011212201220200112... строится так: снача-
ла пишется 0, затем повторяется следующее действие: уже написанную
часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е.
                0 -> 01 -> 0112 -> 01121220 ->...
     Составить алгоритм, который по введенному N, (0<=N<=3000000000)
определяет, какое число стоит на N-ом месте в последовательности.

                            Задача 7.
     Дан массив  X(100)  и  Y(100).  Записать  алгоритм,  меняющий
последовательно местами значения элементов X(k) и  Y(k)  для  этих
таблиц, для k=1,2,...,100, не используя промежуточных переменных.

                            Задача 8.
     Точки с целочисленными координатами из 1-го квадранта помеча-
ются числами 0,1,2,...  слева направо и снизу вверх таким образом,
что очередной точке приписывается минимальное  число,отсутствующее
в  вертикали и горизонтали,проходящей через точку.  Первой помеча-
ется точка (0,0).
     Написать программу,  которая
     1. По заданным координатам x и y, x>=0, y>=0, x,y- целые, оп-
ределяет пометку точки.
     2. По заданной координате x и пометке точки y, x>=0, y>=0, x,
y - целые, определяет вторую координату точки.

                            Задача 9.
     Найти длину  периода и сам период бесконечной степенной дроби
по основанию Р,  представляющей рациональное число N/M (для конеч-
ных дробей  считать,  что  длина  периода равна 1).  M,N,P - целые
десятичные числа, 0<N<M, 1<P.

                           Задача 9.1.
     Для введенных  действительного числа r>0 и натурального числа
qmax необходимо найти наилучшее приближение r в виде  рациональной
дроби p/q, где q<=qmax.

                            Задача 10.
     Известно, что запись числа A в позиционных системах счисления
с основанием p и q имеет вид бесконечной периодической дроби с пе-
риодом 2:
                      A = O,(ab)  = O,(ba)                     (*)
                                p         q
где a и b - различные цифры в этих системах счисления.
     Написать программу, которая для введенных натуральных чисел p
и q (2<=p,q<=30,  p>q) находит и выводит все возможные пары значе-
ний цифр a и b, удовлетворяющих соотношению (*). Если таковых нет,
вывести сообщение 'Пригодных цифр нет'.
     Предусмотреть защиту от ввода ошибочных данных.
     Примечание: Значением числа,  запись которого  в  позиционной
системе счисления с основанием S есть 0,cdef (где c,d,e,f - цифры),
являются
                       c     d     e     f
                     --- + --- + --- + --- .
                      S^1   S^2   S^3   S^4

                            Задача 11.
     Определим множества K[i] рекуррентно.  Пусть  K[0]  =  [0,1].
Разделим  сегмент [0,1] на три части точками 1/3 и 2/3 и удалим из
него интервал (1/3,2/3). Получим множество K[1], состоящее из двух
оставшихся сегментов [0,1/3] и [2/3,1].  Каждый из них разделим на
три части (точками 1/9 и 2/9 для первого сегмента, и точками 7/9 и
8/9 -  для  второго  )  и  удалим  средние  интервалы  (1/9,2/9) и
(7/9,8/9). Таким образом получаем множество K[2],  и т.д. Пусть мы
построим множество K[i]. Поделим каждый оставшийся сегмент из K[i]
на 3 части и удалим из этих сегментов средние интервалы.  Получим,
таким образом, из K[i] множество K[i+1].
     Вводятся 3 целых числа n,a,b.
     Необходимо определить, принадлежит ли точка с координатой
a/b множеству K[n].

                            Задача 12.
     Найти наибольший  общий  делитель  и наименьшее общее кратное
чисел a и b.

                            Задача 13.
     Число называется совершенным, если оно равно сумме всех своих
делителей за исключением  его  самого.  Любое  четное  совершенное
число представимо в виде
                   p-1    p
                  2   * (2  - 1), где р натуральное число.
     Найти двоичное представление  для  максимального совершенного
четного числа меньшего введенного N.

                            Задача 14.
     Заданы натуральные числа E,K,M,T в записи химической  реакции
                       ХеАk + Y -> YmAt + X,
где A,X,Y - атомы или группы атомов.  Написать  алгоритм,  который
находит такие натуральные коэффициенты, чтобы знак "стрелки" можно
было заменить знаком равенства.

                            Задача 15.
     Вводятся целые числа a и b.  Пусть у треугольника ABC коорди-
наты A=(0,0),  B=(a,b),  а обе координаты C=(x,y) - целые числа, и
площадь треугольника ABC не равна нулю.
     Какую минимальную площадь может иметь треугольник ABC?

                            Задача 16.
     Имеется N банок с целочисленными объемами V1, ..., Vn литров,
пустой сосуд и кран с водой.  Можно ли с помощью этих банок налить
в сосуд ровно V литров воды.


                            Задача 17.
     Вычислить число  e  (основание натурального логарифма) с точ-
ностью n значащих десятичных цифр после запятой.  Можно  использо-
вать числовой ряд:
          e=1+1/1!+1/2!+...+1/А!...

                            Задача 18.
     Вывести на экран число 2^n, n<=10000, n - натуральное.

                            Задача 19.
     Определить количество повторений каждой из цифр 0,1,2,...,9 в
числе N^N (N в степени N), N <= 1000.

                           Задача 19.1.
     Определить, можно ли представить заданное натуральное число в
виде произведения четырех последовательных натуральных чисел. Дли-
на числа не более 250 символов. Конец числа - пробел.

                            Задача 20.
     Найти все простые числа, не превосходящие N.

                            Задача 21.
     Вводится N.  Необходимо найти,  на сколько нулей оканчивается
N!=1*2*3*...*N.

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

                            Задача 23.
     Натуральное число  N>1  представить  в виде суммы натуральных
чисел так, чтобы произведение этих слагаемых было максимально.

                            Задача 24.
     Задается любое положительное действительное число R.Найти по-
ложительные действительные R1,R2,...,Rn,  Ri<4 ,i=1,...,n,  такие,
что R=R1*R2*...*Rn=R1+R2+...+Rn

                            Задача 25.
     Даны целые  числа А(0),А(1),...,А(5).  Найти множество корней
уравнения
              А(5)*X^5 + А(4)*X^4 + ... + А(0) = 0,
если известно, что  все корни - целые числа, A(0)<>0.

                            Задача 26.
     Вывести в  порядке  возрастания все обыкновенные несократимые
дроби,  заключенные между 0 и 1,  знаменатели которых не превышают
15. Массив при этом заводить не следует.

                            Задача 27.
     Дан многогранник, в вершинах которого записаны целые числа.
     Одним ходом можно выбрать одно ребро,  и к числу, записанному
в одном из его концов прибавить один,  а из числа,  записанного  в
другом конце - вычесть 1.
     Какому необходимому и достаточному условию должны  удовлетво-
рять записанные числа,  чтобы с помощью таких ходов можно было до-
биться, чтобы во всех вершинах был одновременно записан ноль?  От-
вет обосновать.

                            Задача 28.
    a). Полином
         p(x)=A[n]*x^n+A[n-1]*x^(n-1)+ ...  +A[1]*x+A[0]
задается своими коэффициентами A[n], ... ,A[0]. Найти его значение
P в точке x.
    b). Число в k-ичной системе задается своим представлением
                        (A[n], ... ,A[0]),
т.е. в десятичной системе оно имеет значение
         A[n]*k^n+A[n-1]*k^(n-1)+ ...  +A[1]*k+A[0].
     Найти это значение.

                            Задача 29.

                                   n
     Полином N-ой степени  A(x) = SUM  a[i] * x^i  задается своими
                                  i=0

коэффициентами a[i]. Найти коэффициенты b[i],i=0,...,n*m, m-ой сте-
пени полинома A(x). Числа n,m<=40.

                            Задача 30.
     Вычислить коэффициенты A[1],  A[2],  ..., A[N]
многочлена
            n        n-1
     P(x) =x + A[1]*x   +...+ A[N-1]*x + A[N]
с заданными действительными корнями X[1], X[2], ..., X[N].

                            Задача 31.
                 n
      Многочлен SUM a[i]*x^i задается набором своих коэффициентов
                i=0

a[i], i=0,..,n. Необходимо вычислить коэффициенты b[i] такого мно-
гочлена, что

    n              n
   SUM b[i]*x^i = SUM a[i]*(x+d)^i
   i=0            i=0

для заданного d.

                            Задача 32.
     Вычислить  значение  полинома
                     f(x)=ax^4+bx^3+cx^2+dx+e
для x=1, ..., 10000, используя не более 51000 операций *,+.
