program polynomes; {TP 922 01}

uses crt;

const long    = 250 ;
const deg_nul = -10;    {le degre du polynome nul, par convention}
type poly = array[-1..long] of integer ;
	  
function max(a,b:integer):integer; {comme son nom l'indique ...}
begin
   if a<b then max:=b
   else max:=a
end;

procedure poly_nul(var P:poly);
var i : integer;
begin 
   P[-1]:=deg_nul; 
   for i:=0 to long do
   begin
      P[i]:=0;
   end
end;


procedure saisie(var P:poly);  {saisie au clavier}
var deg,i,aux : integer;
begin	      
   poly_nul(P);
   writeln('entrez le degre, -1 si polynome nul');
   readln(deg);
   if deg>=0 then
   begin
      P[-1]:=deg;
      for i:=0 to deg do
      begin
	 write('coeff X^',i,' ? ');
	 readln(aux);
	 P[i]:=aux;
      end
   end
end;

procedure visu(P:poly);  {visualisation a l'ecran}
var deg,i,dom : integer;
begin	      
   deg := P[-1];
   if deg = deg_nul then
      writeln('polynome nul')
   else
   begin
      {writeln('degre du polynome : ',P[-1]);   }
      dom:=P[P[-1]]; {P[-1] est le degré du polynome P, donc P[P[-1]] est le coeff de plus haut degre}
      if dom=1 then write('X^',P[-1])
      else if dom=-1 then write('-X^',P[-1])
      else write(P[P[-1]],'X^',P[-1]);
      for i:=deg-1 downto 2 do
	 if P[i]>1 then write(' + ',P[i],'X^',i)
	 else if P[i]<-1 then write(' - ',-P[i],'X^',i)
	 else if P[i]=1 then write(' + X^',i)
	 else if P[i]=-1 then write(' - X^',i);
      if P[1]>1 then write(' + ',P[i],'X')
      else if P[1]=1 then write(' + X')
      else if P[i]=-1 then write(' - X')
      else if P[1]<-1 then write(' - ',-P[i],'X');
      if P[0]>0 then write(' + ',P[0])
      else if P[0]<0 then write(' - ',-P[0]);
      writeln
   end
end;

procedure addition(P:poly;Q:poly;var R:poly);
var int_fin : integer; {qd s'arrete-t-on?}
var i	: integer;
var deg	: integer; {nouveau degre}
begin	
   if (P[-1]=Q[-1]) AND (P[-1]=deg_nul) then {cas ou P et Q sont nuls}
      poly_nul(R)
   else
   begin
      int_fin:=max(P[-1],Q[-1]); 
      for i:=0 to int_fin do
      begin
	 R[i]:=P[i]+Q[i];
      end;
      deg:=int_fin;
      while (R[deg]=0) AND (deg>=0) do  {calcul du nouveau degre, on descend tq les coeffs sont nuls}
      begin
	 deg:=deg - 1
      end;
      if deg<0 then R[-1]:=deg_nul else R[-1]:=deg {on peut obtenir R=0 meme si P et Q sont non nuls}
   end
end;

procedure scal_mul(P:poly;c:integer;var R:poly);  {c*P avec c entier}
var i : integer ;
begin 
   poly_nul(R);
   if c<>0 then
   begin
      R[-1]:=P[-1]; {le degré est inchange}
      for i:=0 to P[-1] do R[i]:=c*P[i]
   end
end;

procedure produit(P:poly;Q:poly;var R:poly);
var deg,i,j : integer;
begin	    
   poly_nul(R);
   if (P[-1]<>deg_nul) AND (Q[-1]<>deg_nul) {ni P ni Q ne sont nuls}
      then
   begin
      for i:=0 to long do
      begin
	 for j:=0 to i do R[i]:=R[i]+P[j]*Q[i-j]
      end;
      deg:=long;
      while (R[deg]=0) do  {calcul du nouveau degre}
      begin
	 deg:=deg - 1;
      end;
      R[-1]:=deg
   end
end;

procedure puis_n(P:poly;n:integer;var R:poly);   {P^n avec n entier}
var i : integer;
begin 
   if n=0 then
   begin
      poly_nul(R);
      R[0]:=1;
      R[-1]:=0;
   end
   else
      R:=P;
   if n>1 then
   begin
      for i:=2 to n do
      begin
	 produit(P,R,R); {R<-P.R}
      end;
   end
end;



procedure compose(P:poly;Q:poly;var R:poly);   {R=PoQ}
var q_i, aux : poly;
var i,deg : integer ;
begin	  
   poly_nul(R);
   
   if P[-1]<>deg_nul then
      if Q[-1]=deg_nul then     {cas non indispensable}
      begin
	 if P[0]<>0 then R[-1]:=0 else R[-1]:=deg_nul;
	 R[0]:=P[0]
      end
      else
      begin
	 for i:=0 to P[-1] do
	 begin
	    puis_n(Q,i,q_i); 		{q_i contiend Q^i}
	    scal_mul(q_i,P[i],aux); 	{aux contient P[i].Q^i}
	    addition(R,aux,R) 		{R <- R + P[i].Q^i}
	 end;
	 R[-1]:=P[-1]*Q[-1];
      end
end;


procedure division_exacte(A,B : poly; var res:poly); {A/B avec recursion}
var
   a_soustraire,a_ajouter,reste,quot_reste : poly;
begin
   poly_nul(res);
   if A[-1]<>deg_nul then
   begin
      res[A[-1]-B[-1]]:=A[A[-1]];		{calcul du premier coefficient de res}
      res[-1]:=A[-1]-B[-1];			{degre de res}
      produit(B,res,a_soustraire);		{a_soustraire <- B.res}
      scal_mul(a_soustraire,-1,a_ajouter);	{a_soustraire est l'oppose de a_ajouter}
      addition(A,a_ajouter,reste);		{reste <- A + a_ajouter}
      division_exacte(reste,B,quot_reste);	{quot_reste <- reste/B}
      addition(res,quot_reste,res)		{res <- res + quot_reste}
   end
end;

procedure division_exacte2(A,B : poly; var res:poly); {A/B sans recursion}
var
   a_soustraire,a_ajouter,monome : poly;
begin
   poly_nul(res);
   if A[-1]<>deg_nul then res[-1]:=A[-1]-B[-1];
   while A[-1]<>deg_nul do
   begin
      poly_nul(monome);
      monome[A[-1]-B[-1]]:=A[A[-1]];
      monome[-1]:=A[-1]-B[-1];
      addition(res,monome,res);
      produit(B,monome,a_soustraire);
      scal_mul(a_soustraire,-1,a_ajouter);
      addition(A,a_ajouter,A)
   end;
end;


procedure cyclotomic(n : integer; var C:poly);
var
   cyc_aux : poly;
   i	   : integer;
begin
   poly_nul(C);
   C[-1]:=n; {initialisation de C a X^n-1}
   C[0]:=-1;
   C[n]:=1;  {si n=0, ca marche aussi !}
   for i:=1 to n-1 do if ((n mod i)=0) then
   begin
      cyclotomic(i,cyc_aux);		{cyc_aux <- cyclotomic(i)}
      division_exacte2(C,cyc_aux,C)	{C <- C/cyc_aux}
   end
end;

var
   P,Q,R : poly;
   n	 : integer;
	 
begin
   clrscr;
   writeln('saisie du polynome P');
   saisie(P);
   writeln;
   write('polynome P : ') ; visu(P);
   readln;
   writeln('saisie du polynome Q');
   saisie(Q);
   writeln;
   write('polynome Q : ') ; visu(Q);
   readln;
   poly_nul(R);
   writeln('somme de P et Q:');
   addition(P,Q,R);
   write('polynome P : ') ; visu(P); 
   write('polynome Q : ') ; visu(Q);  
   write('polynome R=P+Q : ') ; visu(R);
   readln;
   writeln('3P : ');
   scal_mul(P,3,R);
   visu(R);
   readln;
   writeln('produit de P et Q:');
   produit(P,Q,R);
   write('polynome P : ') ; visu(P);
   write('polynome Q : ') ; visu(Q); 
   write('polynome R=PQ : ') ; visu(R);
   readln;
   writeln('P puissance 4');
   puis_n(P,4,R);
   write('polynome P : ') ; visu(P); 
   write('polynome R=P^4 : ') ; visu(R);
   readln;
   writeln('P puissance 0');
   puis_n(P,0,R);
   write ('P^0 : ') ; visu(R);
   readln;
   writeln('composee de P et Q : ');
   produit(P,Q,R);
   write('polynome P : ') ; visu(P); 
   write('polynome Q : ') ; visu(Q);  
   write('polynome R=PoQ : ') ; visu(R);
   readln;
   writeln('quotient exact de P par Q : ');
   division_exacte(P,Q,R);
   write('polynome P : ') ; visu(P);  
   write('polynome Q : ') ; visu(Q);  
   write('polynome R=P div Q : ') ; visu(R);
   readln;
   n:=10;
   writeln('cyclo(n) : entrez n :');
   readln(n);
   while n>=0 do
   begin
      cyclotomic(n,R);
      write('cyclotomic ',n,' : ');visu(R);
      writeln('cyclo(n) : entrez n :');
      readln(n)
   end;
end.