In Frage 6 der 58. Olympischen Spiele wurde die Frage der elementaren Ganzzahltheorie gestellt, die als Tradition bezeichnet werden kann.
In diesem Problem wird die Tatsache, dass "es ganze Zahlen x und y gibt, die ax + by = 1 für gegenseitig Primzahlen a und b erfüllen", als allgemeines Wissen im gesunden Menschenverstand verwendet. Hier werde ich das Ergebnis der Implementierung des gesunden Menschenverstandes im gesunden Menschenverstand mit Python berichten.
python
print("Geben Sie zwei positive Ganzzahlen ein, die sich gegenseitig ausschließen.")
a, b= map(int, input().split())
n = 1
r = a**n % b
#print(r)
while r > 1:
n = n + 1
r = a**n % b
#print(r)
m = a**n // b
print(str(a)+"x+"+str(b)+"y=Die ganzen Zahlen x und y, die 1 erfüllen"+str(a**(n-1))+"Wann"+str(-m)+"ist.")
Die Theorie selbst ist Eulers Satz, der früher eingeführt wurde. https://qiita.com/naoya_suzuki/items/5490a1099dee8ad7065e
Wenn Sie a = 6 und b = 11 versuchen, sollten Sie sehen, dass "die ganzen Zahlen x und y, die 6x + 11y = 1 erfüllen, 10077696 und -5496925 sind." Es ist eine überraschend große Zahl, so dass Sie sie nicht finden können, selbst wenn Sie danach suchen, ohne überhaupt eine Richtlinie zu erstellen. (; ^ _ ^ A.
Nachtrag: Wenn Sie darüber nachdenken, können Sie intuitiv x = 2 und y = -1 verstehen.
Recommended Posts