15.1. Остача (теорія цілих чисел)
остача від ділення суми чи добутку цілих чисел залежить відповідно лише від суми чи добутку остач від ділення цих чисел на той самий дільник.
остачі від ділення степеня сталого натурального числа на інше стале натуральне число, починаючи з певної величинии степеня, періодична відносно степеня.
Алгоритм найстисліше можна подати такою програмою.
const m=21.4875626; empty=[];
var s: array[0..255] of set of byte;
a,b,c,d: array[0..99] of longint; o: text;
i,j,k,l,fdiv: word; n,fmod: byte; f,f1: longint; BEGIN
assign(o,'REMAIN.DAT'); reset(o); read(o,n);
for j:=0 to n do read(o,a[j]); close(o);
assign(o,'REMAIN.RES');rewrite(o); d[n]:=a[n]; l:=n; k:=n-1;
while (k>0) and (m>d[k+1]*ln(a[k])) do begin
d[k]:=a[k]; for j:=2 to d[k+1] do d[k]:=a[k]*d[k];
l:=k; dec(k) end;
if l=1 then begin
d[1]:=d[1] mod a[0]; writeln(o,d[1]); close(o); halt end;
b[1]:=a[0];
for k:=1 to l-1 do begin
for j:=0 to 255 do s[j]:=empty;
f:=a[k] mod b[k];
fdiv:=f div 256;
fmod:=f mod 256; i:=1;
repeat include(s[fdiv], fmod); inc(i);
f:=(f*a[k]) mod b[k];
fdiv:=f div 256;
fmod:=f mod 256;
until fmod in s[fdiv]; f1:=f;
f:=1; j:=0;
repeat f:=(f*a[k]) mod b[k]; inc(j);
until f=f1; d[k]:=f; c[k+1]:=j; b[k+1]:=i-j end;
i:=l-1; if d[l] < c[l] then begin
d[i]:=1; for k:=1 to d[l] do d[i]:=a[i]*d[i] mod b[i] end
else begin
k:=(d[l]-c[l]) mod b[l];
for j:=1 to k do d[i]:=a[i]*d[i] mod b[i] end;
if l > 2 then for j:=i downto 2 do begin
k:=(d[j]-c[j]) mod b[j]; if k < b[j] then k:=k+b[j];
i:=j-1; for l:=1 to k do d[i]:=a[i]*d[i] mod b[i] end;
writeln(o,d[1]); close(o); end.15.2. Множення (оптимізований перебір)
Встановити, де стоять нулі у другому множнику.
Встановити, які знаки потрібно відновити.
Реалізувати перебір цифр першого співмножника і цифр другого співмножника у порядку зростання старшинства розрядів з оптимізацією —узгодженням результату дії множення першого множника на цифру другого множника.
Врахувати, що результат множення числа на цифру, відмінну від 0, має таку саму кількість цифр або на 1 більшу.