fork download
copy 
  1. # Titel: Verallgemeinerter Chinesischer Restsatz
  2. # Autor: Manuel Stuebler
  3.  
  4. # einfacher euklidscher Algorithmus
  5. def euklid(a, b):
  6.     while b != 0:
  7.         a, b = b, a % b
  8.     return a
  9.  
  10. # induktiver, erweiterter euklidscher Algorithmus
  11. # liefert zus. die Faktoren x, y der Linearkombination
  12. def erwEuklid(a, b):
  13.     # Hilfsvariablen
  14.     u, s, v, t = 1, 0, 0, 1
  15.     while b != 0:
  16.         q = a//b # Quotient q
  17.         u, s, v, t = s, u-q*s, t, v-q*t
  18.         a, b = b, a % b # Rest r
  19.     return a, u, v
  20.  
  21. # das Inverse von a bez. b mit dem erweiterten
  22. # euklidschen Algorithmus berechnen
  23. def inverse(a,b):
  24.     (c, x, y) = erwEuklid(a, b)
  25.     return x
  26.  
  27. # den verallgemeinerten chinesischen Restsatz anwenden
  28. def vcrs(c):
  29.     k = len(c) # Anzahl der Kongruenzen
  30.     #print("k = " + str(k))
  31.  
  32.     # initialer Wert entspricht der ersten Kongruenz a_0 mod m_0
  33.     a, M = c[0]
  34.     #print("a, M = " + str((a, M)))
  35.  
  36.     # c[i][0] -> a_i , c[i][1] -> m_i
  37.     # fuer jede weitere Kongruenz iterativ ein mit der bisher
  38.     # gefundenen Loesung vertraegliches Ergebnis berechnen
  39.     for i in range(1, k):
  40.         # j = Differenz aus aktuellem a_i und vorangegangem
  41.         # Ergebnis a mod M der bisher betrachteten Kongruenzen 0..i
  42.         j = c[i][0] - a
  43.         #print("c (" + str(i) + ") = " + str(j))
  44.  
  45.         (d, x, y) = erwEuklid(M, c[i][1])
  46.         #print(str(d) + " = " + str(x) + "*" + str(M) +
  47.         #      " + " + str(y) + "*" + str(c[i][1]))
  48.  
  49.         # d muss j teilen, damit sich die neue Kongruenz
  50.         # in das bisher gefundene Ergebnis a mod M einreiht
  51.         if ((j % d) != 0):
  52.            print("Es existiert keine Loesung.")
  53.            return (-1,-1)
  54.  
  55.         Mt = M # temporaer Zwischenspeichern fuer a = ...
  56.         M = c[i][1]*M//d # neuen Modul M berechnen
  57.         a = (a + Mt*j*x//d) % M # neues a mod M berechnen
  58.  
  59.     return (a % M, M) # Ergebnis a mod M zurueckgeben
  60.  
  61.  
  62. # Eingabe und Ausgabe
  63. def main():
  64.  
  65.     l = [] # Tripel in diese Liste einlesen
  66.  
  67.     while True:
  68.         try:
  69.             s = input()
  70.             if (len(s) < 5):
  71.                 continue
  72.             b = tuple(s.split())
  73.             a = (int(b[0]), int(b[1]), int(b[2]))
  74.             l.append(a)
  75.         except:
  76.             break
  77.  
  78.     # durch Kuerzen bzw. Multiplikation mit dem jeweils Inversen
  79.     # wird der Vorfaktor a eliminiert -> x = b_neu mod m_neu
  80.     c = []
  81.  
  82.     for t in l:
  83.         g = euklid(t[0], t[2])
  84.  
  85.         # der ggT ist != 1 -> Kuerzen der Kongruenz (a_neu=1,b_neu=b/a)
  86.         # dabei muss der Modul um den ggT reduziert werden (m_neu=m/ggT)
  87.         if (g != 1):
  88.             if ((t[0] == g) and (t[1] % g) == 0):
  89.                 c.append((t[1]//t[0], t[2]//g))
  90.             else:
  91.                 print("Es existiert keine Loesung.")
  92.         # ist der ggT = 1 so kann das Inverse bestimmt werden
  93.         # und mit a, sowie b multipliziert werden (a_neu=1,b_neu=a*inv(a))
  94.         else:
  95.             i = inverse(t[0], t[2])
  96.             i = i % t[2]
  97.             c.append((t[1]*i,t[2]))
  98.  
  99.     # loesen des Systems von Kongruenzen
  100.     ret = vcrs(c)
  101.  
  102.     if (ret != (-1,-1)):
  103.         # und entsprechend formatiert ausgeben
  104.         print(str(ret[0]) + " " + str(ret[1]))
  105.  
  106.  
  107. if __name__ == "__main__":
  108.   main()
  109.  
Success #stdin #stdout 0.03s 9748KB
comments (?)
stdin
copy 
13 23 34
11 7 15
14 20 38
1 2 3
11 0 23
14 10 48
22 2 24
stdout
copy 
Es existiert keine Loesung.
Es existiert keine Loesung.
Es existiert keine Loesung.
5957 11730
https://ideone.com/aBgnkB
language:
Python 3 (python  3.12)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!