From 0be2be0a92f992bf8ee9eff701cb19658a1e7544 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Thu, 29 Dec 2022 15:20:32 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D1=8B?=
 =?UTF-8?q?=20=D0=BB=D0=B0=D0=B1=D1=8B=208-15?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 lab13/lab13.py | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)
 create mode 100644 lab13/lab13.py

(limited to 'lab13')

diff --git a/lab13/lab13.py b/lab13/lab13.py
new file mode 100644
index 0000000..993ad81
--- /dev/null
+++ b/lab13/lab13.py
@@ -0,0 +1,77 @@
+def poly_print(f):
+    n, f_c = f
+    n = len(f_c) - 1
+    poly_str = ""
+    for i in range(len(f_c)):
+        cur_cf = f_c[i]
+        if not cur_cf:
+            continue
+        if cur_cf > 0:
+            sign = "+"
+        else:
+            cur_cf = -cur_cf
+            sign = "-"
+        poly_str += f"{sign} {cur_cf}x^{n - i} "
+    poly_str = poly_str[:len(poly_str) - 4]
+    if poly_str[0] == "+":
+        poly_str = poly_str[2:]
+    return poly_str
+
+
+def poly_reduction(f):
+    n, f_c = f
+    i = 0
+    while i < len(f_c) and f_c[i] == 0:
+        n -= 1
+        i += 1
+    return n, f_c[i:]
+
+
+def inverse(n, field):
+    x = 0
+    for _ in range(field):
+        if (n * x) % field != 1:
+            x += 1
+        else:
+            break
+    return x
+
+
+def pdf(f, g, field):
+    m, f_c = f
+    n, g_c = g
+    f_c.reverse()
+    g_c.reverse()
+
+    q_c = [0] * (m + 1)
+    r_c = f_c
+
+    for k in range(m - n, -1, -1):
+        q_c[k] = (f_c[n + k] * inverse(g_c[n], field)) % field
+        for j in range(n + k - 1, k - 1, -1):
+            r_c[j] = (r_c[j] - q_c[k] * g_c[j - k]) % field
+
+    q_c.reverse()
+    r_c.reverse()
+
+    return (m, q_c), (n, r_c)
+
+
+if __name__ == "__main__":
+    print("Введите коэффициенты первого многочлена:")
+    cf = list(map(int, input().split()))
+    f = poly_reduction((len(cf) - 1, cf))
+
+    print("Введите коэффициенты второго многочлена:")
+    cf = list(map(int, input().split()))
+    g = poly_reduction((len(cf) - 1, cf))
+
+    f_size = int(input("Введите размерность поля: "))
+
+    q, r = pdf(f, g, f_size)
+
+    print("Результат деления:", poly_print(q))
+    if r is not None:
+        print("Остаток от деления:", poly_print(r))
+    else:
+        print("Остатка нет")
-- 
cgit v1.2.3