Дистанционная подготовка к Всероссийской олимпиаде по информатике

ДВГУПС, преподаватель программы IT-школа Samsung,
Пономарчук Юлия Викторовна
E-mail: yulia.ponomarchuk@gmail.com

a, b – целые числа,
x, y – коэффициенты Безу

Сложность алгоритма O(log2a)
Алгоритм:
НА ВХОДЕ: два неотрицательных числа a и b: a>=b НА ВЫХОДЕ: d=НОД(a,b) и целые x,y: ax + by = d. 1. Если b=0 положить d:=a, x:=1, y:=0 и возвратить (d,x,y)
2. Положить x2:=1, x1:=0, y2:=0, y1:=1 3. Пока b>0 3.1 q:=[a/b], r:=a-qb, x:=x2-qx1, y:=y2-qy1 3.2 a:=b, b:=r, x2:=x1, x1:=x, y2:=y1, y1:=y 4. Положить d:=a, x:=x2, y:=y2 и возвратить (d,x,y)

var  
x1,y1,x2,y2,q,r:Longint;
begin  
if b=0 then  

begin    
d:=a;  x:=1;  y:=0  
end  
else  
begin    
x1:=0; x2:=1; y1:=1; y2:=0;    
while b>0 do    
begin      
q:=a div b;      
r:=a-q*b;      
x:=x2-q*x1;      
y:=y2-q*y1;      
a:=b; b:=r; x2:=x1;  x1:=x;  y2:=y1;  y1:=y    
end;    
d:=a; x:=x2; y:=y2  
end;
end;

виде xq=(an an-1…a0 a-1 a-2 … a-m)q,
где ai  – цифра соответствующей системы

счисления, находящаяся в позиции i, сводится к вычислению значения многочлена 

где q – основание системы счисления. В случае отрицательного основания q имеем сумму знакопеременной последовательности – члены с четными степенями положительны, а с нечетными – отрицательны.

Решение задачи 1

Минимальная целая степень, в которую нужно возвести число –2, чтобы

получить число, превосходящее 381, есть 10 ((-2)10 = 1024).
Добавим к нему число (-2)9= -512, получим 512. Это больше, чем 381.
Значит, нужно добавить еще отрицательное число, например, 
(-2)7= -128, получим 512-128=384.
Результат все еще больше 381, поэтому добавляем еще отрицательное число (-2)3= -8 и получаем 384-8=376, что меньше, чем 381.
Теперь добавим два положительных числа (-2)2 =4 и (-2)0 = 1. Мы получим 376+4+1=381. Значит, можно записать 

Решение задачи 1

если их наибольший общий делитель равен 1.
Несколько натуральных чисел

называются попарно взаимно простыми, если каждое из этих чисел является взаимно простым с каждым другим из них.
Например, 10, 11, 21 – попарно взаимно простые числа, а 10, 11, 25 таковыми не являются.
Сколько троек попарно взаимно простых чисел можно составить из двузначных натуральных чисел?

При этом придется перебирать все возможные тройки двузначных натуральных чисел

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

mod Y; if Rest=0 then goto P6; X:=Y;Y:=Rest; goto P4;

P6: NOD:=Y; end; var I,J,K,Coprime_N:longint; begin Coprime_N:=0; for I:=10 to 97 do  for J:=I+1 to 98 do    for K:=J+1 to 99 do    if (NOD(I,J)*NOD(J,K)*NOD(I,K))=1 then     Coprime_N:= Coprime_N+1;    writeln ('Three Coprime Numbers=', Coprime_N);    readln;    end.

Ответ: 34 040 троек

выглядит следующим образом: 0, 1, 1, 2, 3, 5, 8,

13, 21, 34, 55, 89, 144, …
Любое натуральное число можно представить в виде суммы неповторяющихся чисел Фибоначчи, например:  
7=5+2, 20=13+5+2, 33=21+8+3+1 и так далее.
Закодируем натуральное число следующим образом:
если в сумме присутствует число Фибоначчи с номером n, то в соответствующей позиции, начиная справа, ставится единица;
если число Фибоначчи с номером n отсутствует в сумме, в соответствующей позиции ставится ноль, например: 

Тогда число 45274 в данной кодировке имеет вид …

to 50 do Fibo_Code[Count]:=0; Count:=1; while(n1-Fibo(Count)>=0) do Count:=Count+1; Max_code:=Count-1; repeat

Count:=1; while(n1-Fibo(Count)>=0) do Count:=Count+1; Fibo_Code[Count-1]:=1; n1:=n1-Fibo(Count-1); until(n1=0);   for Count:=Max_Сode downto 1 do   write(Fibo_Code[Count]:1); writeln;   readln; end.

(X

с основанием q.
После успешного решения задачи случился новогодний праздник, в

ходе которого были утеряны результаты решения задачи, результаты преобразования исходного числа в систему счисления с основанием q  и само основание системы счисления.
В ходе коллективного мозгового штурма удалось вспомнить, что основание системы счисления было натуральным числом, меньшим 100.
Также вспомнилось, что в числе, полученном в результате преобразования исходного числа,
не было нулей и единиц,
содержалось две цифры «2»,
одна цифра «3»,
одна цифра «4»
и не было ни одной цифры «5».
Были там еще какие-то цифры. Но их вспомнить не удалось.
Восстановите основание системы счисления, в которую нужно перевести исходное число .

Задача 4