Формат входного файла

Файл содержит четыре натуральных числа a,b,c,d (1 <= a,b,c,d<= 90000).

Формат выходного файла

Файл должен содержать два натуральных взаимно простых числа - числитель и знаменатель полученной дроби.

Пример

Input.txt	Output.txt
1 2 1 4	3 4

Промежуточные результаты не превышают longint.

Program slojdrobej1;

const nmax=100;

var

a,b,c,d,x,y,nodxy:longint;

function nod(a,b:longint):longint;

var aa,ab,ba,bb:longint;

begin

if (a=0)or(b=0) then nod:=a+b

else

if a>b then nod:=nod(a mod b,b)

else nod:=nod(a,b mod a)

end;

begin

assign(input,'input.txt'); reset(input);

assign(output ,'output.txt');

rewrite(output);

read(a,b,c,d);

x:=a*d+b*c;

y:=b*d;

nodxy:=nod(x,y);

x:=x div nodxy;

y:=y div nodxy;

write(x,' ',y);

close(input);

close(output);

end.

Промежуточные результаты превышают longint.

Используем тот факт, что NOD(a,b)=NOD(a-trunc(a/b)*b,b), если a>b

И NOD(a,b)=NOD(a,b-trunc(b/a)*a), если a<b

const nmax=100;

var a,b,c,d,x,y,nodxy:extended;

function nod(a,b:extended):extended;

begin

while (a>0)and(b>0) do

begin

if a>b

then a:=a-trunc(a/b)*b

else b:=b-trunc(b/a)*a;

end;

nod:=a+b;

end;

begin

assign(input,'input.txt'); reset(input);

assign(output ,'output.txt'); rewrite(output);

read(a,b,c,d);

x:=a*d+b*c;

y:=b*d;

nodxy:=nod(x,y);

x:=x/nodxy;

y:=y/nodxy;

write(x:0:0,' ',y:0:0);

close(input);

close(output);

end.

Опр.Уравнение вида ax+by=c называется диафантовым по имени греческого математика Диафанта. Числа a,b,c целые.

задачи

Задача 19 Нахождение частного решения диафантова уравнения ax+by=с

Справедливо следующее утверждение: существует целые числа x и y такие, что ax+by = НОД(a, b).

Доказательство. Находя НОД по алгоритму Евклида, мы, по сути дела, записали следующие равенства: a = q₁b+r₁, b = q₂r₁+r₂, …, r_n = q_n+2r_n+1+r_n+2, r_n+1 = q_n+3r_n+2. Причем НОД(a, b) = r_n+2. Развернем эту цепочку равенств в другую сторону: НОД(a, b) = r_n+2 = r_n-q_n+2r_n+1 = r_n-q_n+2(r_n-1-q_n+1r_n) = -q_n+2r_n-1+(1+q_n+2q_n+1)r_n = kr_n-1+lr_n = … = Ab+Br₁ = Ab + B(a-q₁b) = Ba + (A-Bq₁)b = ax + by, что и требовалось доказать. Сначала решим уравнение ax+by=1. Пусть a>=b>0. По алгоритму Эвклида находим НОД.

Удобно ввести обозначения k₀=0, t_-1=0 и t₀=1;

a=q₁b+r₁.

r₁₌a-q₁b

r₁₌1a-q₁b= k₁a+t₁b , где k₁=1, t₁= t_-1-q₁t₀

b=q₂r₁+r₂

r₂₌b-q₂r₁

r₂=b-(k₁a+t₁b)q₂=-k₁a+(1-t₁q₂)b= k₂a+t₂b , где k₂= k₀-k₁ q₂, t₂= t₀-t₁q₂

r₁=q₃r₂+r₃

r₃= r₁-q₃r₂

r₃= k₁a+t₁b -(k₂a+t₂b)q₃=(k₁ –k2q3)a+(t1-t₂q₃)b= k₃a+t₃b ,

где k₃= k₁-k₂ q₃, t₃= t₁-t₂q₃

и так далее пока не получим r_i =1. Тогда k_i и t_i будут решениями диафантова уравнения ax+by=1.

задачи

Задача 20 Нахождение общего решение уравнения ax+by=c

const nmax=100;

var kw,tw,k0,k1,t0,t1,d,q,r,a,b,c,x,y:longint;

log:boolean;

procedure init;

var p:longint;

begin

log:=false;

assign(input,'input.txt'); reset(input);

read(a,b,c);

x:=1;y:=1;

if (a<0)and(b>0) then begin x:=-1;y:=1; a:=-a;end; делаем a и b положительными и

if (a>0)and(b<0)

then begin x:=1;y:=-1; b:=-b; end;

if (a<0)and(b<0)

then begin x:=-1;y:=-1; a:=-a;b:=-b;end; запоминаем знаки a и b;

if a<b then

begin p:=a;a:=b;b:=p;log:=true; end; если a<b, если a<b, то меняем их

close(input); местами и запоминаем этот факт

end;

function nod(a,b:longint):longint; функция нахождения НОД

begin

if (a=0)or(b=0) then nod:=a+b

else

if a>b then nod:=nod(a mod b,b)

else nod:=nod(a,b mod a);

end;

procedure out; так как в программе мы решаем

уравнение ax+by=1, a>0.b>0 то

begin умножаем найденные значения x и y на с.

assign(output ,'output.txt');

rewrite(output);

if log then write(c*t1*x,' ',c*k1*y)

else write(c*k1*x,' ',c*t1*y);

end;

procedure solve;

begin

d:=nod(a,b);

a:=a div d;

b:=b div d;

c:=c div d; находим НОД и делим на него уравнение

q:=a div b; находим частное

k0:=0;k1:=1; вычисляем первые коэффициенты

t0:=1;t1:=-q*t0;

r:= a mod b; находим остаток

if r=0 then если остаток =0, (это значит b=1),то

begin

k1:=1;t1:=-(a-1);out; halt;

end; сразу находим решение

repeat иначе запускаем цикл по алгоритму Эвклида

a:=b;

b:=r;

if b=1 then exit; если b=1, то решение уже найдено

q:=a div b; иначе продолжаем процесс

kw:=k1;tw:=t1; запоминаем k1 и t1.

k1:=k0-q*k1; вычисляем новые k1 и t1.

t1:=t0-q*t1;

k0:=kw; перебрасываем k1 в k0 и t1 в t0.

t0:=tw;

r:= a mod b; находим новый остаток.

until r=1;

end;

begin init; solve; out; end.

задачи

Задача 21 Индийский алгоритм вычисления степени xⁿ

По определению степени с натуральным показателем xⁿ=x*x*…x, где x взято сомножителем n раз.

Выражение xⁿ называется степень, x – основание степени, n – показатель степени. Если n-нечетное, то xⁿ=x*(x ^{n div 2})², если четное, то xⁿ=(x ^{n div 2})².

Построим нерекурсивный алгоритм вычисления степени xⁿ.

В следующей функции произведение степеней накапливается в переменной t, а степени двойки – в переменной х:

Нерекурсивная реализация индийского алгоритма.

function step(x,m:longint):longint;

var t:longint;

log:boolean;

begin

t:=1; log:=true;

while log do

begin

if odd(m) then t:=t*x; если число m нечетное

m:=m div 2; уменьшаем m в два раза

if m>0 then x:=x*x

else log:=false;

end;

step:=t;

end;

Рекурсивная реализация индийского алгоритма.

Program stepenj;

var p,a,n:longint;

function step(x,m:longint):longint;

var t:longint;

begin

if m=1 then

begin step:=x;exit end если показатель степени равен 1, то

значение функции равно x

else

begin

if odd(n) если m нечетное

then step:=x*sqr(step(x,m div 2))

else step:=sqr(step(x,m div 2)); если m четное

end;

end;

begin

assign(input,’input.txt’);

reset(input);

assign(output,’output.txt’);

rewrite(output);

read(a,n);

p:=step(a,n);

write(p);

end.

задачи