Таблица степеней для полинома - C# (185996)

Формулировка задачи:

Как написать таблицу степеней для полинома, чтобы при возведение в степень результат брался по модулю, если его степень больше необходимой. например, наш неприводимый многочлен x^5+x^2+1. строим таблицу x=x,x^2=x^2,x^4=x^4 а при x^8=x^3+x^2+1(x^8 поделили на неприводимый многочлен так как степень больше 5)

Решение задачи: «Таблица степеней для полинома»

textual
                            Листинг программы 
                        

                            using System;
using System.Collections.Generic;
using System.Linq;
 
namespace ConsoleApplication207
{
    class Program
    {
        [STAThread]
        static void Main(string[] args)
        {
            Polynom p1 = "x16";
            Polynom p2 = "x5 + x2 + 1";
 
            var res = p1 % p2;//получаем остаток от деления
 
            Console.WriteLine(res);// x^4 + x^3 + x + 1
            //
            Console.ReadLine();
        }
    }
 
    /// <summary>
    /// Полином
    /// </summary>
    class Polynom : HashSet<int>//полином это множество степеней
    {
        public Polynom Clone()
        {
            var res = new Polynom();
            foreach (var elem in this)
                res.Add(elem);
            return res;
        }
 
        public Polynom()
        {
        }
 
        public Polynom(params int[] powers) : base(powers)
        {
        }
 
        /// <summary>
        /// Максимальная степень
        /// </summary>
        public int MaxPower
        {
            get { return Count == 0 ? -1 : this.Max(); }
        }
 
        /// <summary>
        /// Парсим строку в полином
        /// </summary>
        public static Polynom Parse(string str)
        {
            var res = new Polynom();
            foreach(var part in str.ToLower().Replace(" ", "").Trim().Split('+'))
            {
                if (part == "1") res.Add(0);
                else
                if (part == "x") res.Add(1);
                else
                if (part.StartsWith("x^")) res.Add(int.Parse(part.Substring(2)));
                else
                if (part.StartsWith("x")) res.Add(int.Parse(part.Substring(1)));
                else
                    throw new Exception("Syntax error");
            }
 
            return res;
        }
 
        /// <summary>
        /// Оператор вычитания
        /// </summary>
        public static Polynom operator -(Polynom p1, Polynom p2)
        {
            var res = new Polynom();
 
            foreach (var elem in p1)
            if(!p2.Contains(elem))
                res.Add(elem);
 
            foreach (var elem in p2)
            if (!p1.Contains(elem))
                res.Add(elem);
 
            return res;
        }
 
        /// <summary>
        /// Оператор умножения
        /// </summary>
        public static Polynom operator *(Polynom p1, Polynom p2)
        {
            var res = new Polynom();
 
            foreach (var elem in p1)
            foreach (var elem2 in p2)
                res.Add(elem + elem2);//степени складываются
 
            return res;
        }
 
        /// <summary>
        /// Остаток от деления
        /// </summary>
        public static Polynom operator %(Polynom dividend, Polynom divisor)
        {
            var res = dividend.Clone();
 
            while (res.MaxPower >= divisor.MaxPower)
            {
                var m = res.MaxPower - divisor.MaxPower;//на какую степень нужно умножить делитель?
                var mm = divisor * new Polynom(m);//умножаем
                res -= mm;//отнимаем
            }
 
            return res;
        }
 
        /// <summary>
        /// Неявное преобразование из строки
        /// </summary>
        public static implicit operator Polynom(string str)
        {
            return Parse(str);
        }
 
        public override string ToString()
        {
            return string.Join(" + ", this.OrderBy(e => -e).Select(x=>x==0?"1":x==1?"x":("x^" + x)));
        }
    }
}
                        