Π£Π³Π»Π΅ΡΠΎΠ΄Π½ΡΠ΅ Π½Π°Π½ΠΎΡΡΡΠ±ΠΊΠΈ.
ΠΠ°Π½ΠΎΡΠ΅Ρ
Π½ΠΎΠ»ΠΎΠ³ΠΈΠΈ Π² ΡΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΡΡΠΈ
ΠΡΠ΅Π΄ΡΠΊΠ°Π·Π°Π½ΠΈΠ΅ ΡΠΈΠ·ΠΈΠΊΠΎ-Ρ ΠΈΠΌΠΈΡΠ΅ΡΠΊΠΈΡ ΡΠ²ΠΎΠΉΡΡΠ² Π½ΠΎΠ²ΡΡ ΡΠ³Π»Π΅ΡΠΎΠ΄Π½ΡΡ ΠΌΠ°ΡΠ΅ΡΠΈΠ°Π»ΠΎΠ² ΠΎΡΡΡΠ΅ΡΡΠ²Π»ΡΠ΅ΡΡΡ ΠΊΠ°ΠΊ Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΠΊΠ²Π°Π½ΡΠΎΠ²ΡΡ ΠΌΠΎΠ΄Π΅Π»Π΅ΠΉ, ΡΠ°ΠΊ ΠΈ ΡΠ°ΡΡΠ΅ΡΠΎΠ² Π² ΡΠ°ΠΌΠΊΠ°Ρ ΠΌΠΎΠ»Π΅ΠΊΡΠ»ΡΡΠ½ΠΎΠΉ Π΄ΠΈΠ½Π°ΠΌΠΈΠΊΠΈ. ΠΠ°ΡΡΠ΄Ρ Ρ ΠΎΠ΄Π½ΠΎΡΠ»ΠΎΠΉΠ½ΡΠΌΠΈ ΡΡΡΠ±ΠΊΠ°ΠΌΠΈ ΠΈΠΌΠ΅Π΅ΡΡΡ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡ ΡΠΎΠ·Π΄Π°Π²Π°ΡΡ ΠΈ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»ΠΎΠΉΠ½ΡΠ΅ ΡΡΡΠ±ΠΊΠΈ. ΠΠ»Ρ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π° Π½Π°Π½ΠΎΡΡΡΠ±ΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ ΡΠΏΠ΅ΡΠΈΠ°Π»ΡΠ½ΡΠ΅ ΠΊΠ°ΡΠ°Π»ΠΈΠ·Π°ΡΠΎΡΡ. Π ΠΈΡΡΠ½ΠΎΠΊ ΠΠ΅Ρ ΠΈΡΠ°Π»ΡΠ½ΡΠ΅ Π½Π°Π½ΠΎΡΡΡΠ±ΠΊΠΈ: Π° — Π‘ (n', n) — ΠΌΠ΅ΡΠ°Π»; Π±-Π‘ (n, 0):mod (n, 3) = 0… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
Π£Π³Π»Π΅ΡΠΎΠ΄Π½ΡΠ΅ Π½Π°Π½ΠΎΡΡΡΠ±ΠΊΠΈ. ΠΠ°Π½ΠΎΡΠ΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΠΈ Π² ΡΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΡΡΠΈ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
Π£Π³Π»Π΅ΡΠΎΠ΄Π½ΡΠ΅ Π½Π°Π½ΠΎΡΡΡΠ±ΠΊΠΈ. ΠΠ· ΡΠ³Π»Π΅ΡΠΎΠ΄Π° ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΡΡΠΈΡΡ ΠΌΠΎΠ»Π΅ΠΊΡΠ»Ρ Ρ Π³ΠΈΠ³Π°Π½ΡΡΠΊΠΈΠΌ ΡΠΈΡΠ»ΠΎΠΌ Π°ΡΠΎΠΌΠΎΠ². Π’Π°ΠΊΠ°Ρ ΠΌΠΎΠ»Π΅ΠΊΡΠ»Π°, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ Π‘=1 000 000, ΠΌΠΎΠΆΠ΅Ρ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΡ ΡΠΎΠ±ΠΎΠΉ ΠΎΠ΄Π½ΠΎΡΠ»ΠΎΠΉΠ½ΡΡ ΡΡΡΠ±ΠΊΡ Ρ Π΄ΠΈΠ°ΠΌΠ΅ΡΡΠΎΠΌ ΠΎΠΊΠΎΠ»ΠΎ Π½Π°Π½ΠΎΠΌΠ΅ΡΡΠ° ΠΈ Π΄Π»ΠΈΠ½ΠΎΠΉ Π² Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ Π΄Π΅ΡΡΡΠΊΠΎΠ² ΠΌΠΈΠΊΡΠΎΠ½. ΠΠ° ΠΏΠΎΠ²Π΅ΡΡ Π½ΠΎΡΡΠΈ ΡΡΡΠ±ΠΊΠΈ Π°ΡΠΎΠΌΡ ΡΠ³Π»Π΅ΡΠΎΠ΄Π° ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Ρ Π² Π²Π΅ΡΡΠΈΠ½Π°Ρ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΡΡ ΡΠ΅ΡΡΠΈΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠΎΠ². ΠΠΎΠ½ΡΡ ΡΡΡΠ±ΠΊΠΈ Π·Π°ΠΊΡΡΡΡ Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΡΠ΅ΡΡΠΈ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΡΡ ΠΏΡΡΠΈΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠΎΠ². Π‘Π»Π΅Π΄ΡΠ΅Ρ ΠΎΡΠΌΠ΅ΡΠΈΡΡ ΡΠΎΠ»Ρ ΡΠΈΡΠ»Π° ΡΡΠΎΡΠΎΠ½ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΡΡ ΠΌΠ½ΠΎΠ³ΠΎΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠΎΠ² Π² ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ Π΄Π²ΡΡ ΠΌΠ΅ΡΠ½ΡΡ ΠΏΠΎΠ²Π΅ΡΡ Π½ΠΎΡΡΠ΅ΠΉ, ΡΠΎΡΡΠΎΡΡΠΈΡ ΠΈΠ· Π°ΡΠΎΠΌΠΎΠ² ΡΠ³Π»Π΅ΡΠΎΠ΄Π°, Π² ΡΡΡΡ ΠΌΠ΅ΡΠ½ΠΎΠΌ ΠΏΡΠΎΡΡΡΠ°Π½ΡΡΠ²Π΅.
Π ΠΈΡΡΠ½ΠΎΠΊ ΠΠ΅Ρ ΠΈΡΠ°Π»ΡΠ½ΡΠ΅ Π½Π°Π½ΠΎΡΡΡΠ±ΠΊΠΈ: Π° — Π‘ (n', n) — ΠΌΠ΅ΡΠ°Π»; Π±-Π‘ (n, 0):mod (n, 3) = 0 — ΠΏΠΎΠ»ΡΠΌΠ΅ΡΠ°Π»Π» mod (n, 3)≠ 0 — ΠΏΠΎΠ»ΡΠΏΡΠΎΠ²ΠΎΠ΄Π½ΠΈΠΊ.
Π ΠΈΡΡΠ½ΠΎΠΊ ΠΠ·ΠΎΠ³Π½ΡΡΠ°Ρ ΡΡΡΠ±ΠΊΠ° ΠΡΠ°Π²ΠΈΠ»ΡΠ½ΡΠ΅ ΡΠ΅ΡΡΠΈΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠΈ ΡΠ²Π»ΡΡΡΡΡ ΡΡΠ΅ΠΉΠΊΠΎΠΉ Π² ΠΏΠ»ΠΎΡΠΊΠΎΠΌ Π³ΡΠ°ΡΠΈΡΠΎΠ²ΠΎΠΌ Π»ΠΈΡΡΠ΅, ΠΊΠΎΡΠΎΡΡΠΉ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ²Π΅ΡΠ½ΡΡΡ Π² ΡΡΡΠ±ΠΊΠΈ ΡΠ°Π·Π»ΠΈΡΠ½ΠΎΠΉ Ρ ΠΈΡΠ°Π»ΡΠ½ΠΎΡΡΠΈ. ΠΡΠ°Π²ΠΈΠ»ΡΠ½ΡΠ΅ ΠΏΡΡΠΈΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠΈ (ΡΠ΅ΠΌΠΈΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠΈ) ΡΠ²Π»ΡΡΡΡΡ Π»ΠΎΠΊΠ°Π»ΡΠ½ΡΠΌΠΈ Π΄Π΅ΡΠ΅ΠΊΡΠ°ΠΌΠΈ Π² Π³ΡΠ°ΡΠΈΡΠΎΠ²ΠΎΠΌ Π»ΠΈΡΡΠ΅, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡΠΈΠΌΠΈ ΠΏΠΎΠ»ΡΡΠΈΡΡ Π΅Π³ΠΎ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΡΡ (ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΡ) ΠΊΡΠΈΠ²ΠΈΠ·Π½Ρ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΠΈ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΡΡ ΠΏΡΡΠΈ-, ΡΠ΅ΡΡΠΈΠΈ ΡΠ΅ΠΌΠΈΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠΎΠ² ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡ ΠΏΠΎΠ»ΡΡΠ°ΡΡ ΡΠ°Π·Π½ΠΎΠΎΠ±ΡΠ°Π·Π½ΡΠ΅ ΡΠΎΡΠΌΡ ΡΠ³Π»Π΅ΡΠΎΠ΄Π½ΡΡ ΠΏΠΎΠ²Π΅ΡΡ Π½ΠΎΡΡΠ΅ΠΉ Π² ΡΡΠ΅Ρ ΠΌΠ΅ΡΠ½ΠΎΠΌ ΠΏΡΠΎΡΡΡΠ°Π½ΡΡΠ²Π΅. ΠΠ΅ΠΎΠΌΠ΅ΡΡΠΈΡ ΡΡΠΈΡ Π½Π°Π½ΠΎΠΊΠΎΠ½ΡΡΡΡΠΊΡΠΈΠΉ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅Ρ ΠΈΡ ΡΠ½ΠΈΠΊΠ°Π»ΡΠ½ΡΠ΅ ΡΠΈΠ·ΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΈ Ρ ΠΈΠΌΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΡΠ²ΠΎΠΉΡΡΠ²Π° ΠΈ, ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡ ΡΡΡΠ΅ΡΡΠ²ΠΎΠ²Π°Π½ΠΈΡ ΠΏΡΠΈΠ½ΡΠΈΠΏΠΈΠ°Π»ΡΠ½ΠΎ Π½ΠΎΠ²ΡΡ ΠΌΠ°ΡΠ΅ΡΠΈΠ°Π»ΠΎΠ² ΠΈ ΡΠ΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΠΉ ΠΈΡ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π°.
ΠΡΠ΅Π΄ΡΠΊΠ°Π·Π°Π½ΠΈΠ΅ ΡΠΈΠ·ΠΈΠΊΠΎ-Ρ ΠΈΠΌΠΈΡΠ΅ΡΠΊΠΈΡ ΡΠ²ΠΎΠΉΡΡΠ² Π½ΠΎΠ²ΡΡ ΡΠ³Π»Π΅ΡΠΎΠ΄Π½ΡΡ ΠΌΠ°ΡΠ΅ΡΠΈΠ°Π»ΠΎΠ² ΠΎΡΡΡΠ΅ΡΡΠ²Π»ΡΠ΅ΡΡΡ ΠΊΠ°ΠΊ Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΠΊΠ²Π°Π½ΡΠΎΠ²ΡΡ ΠΌΠΎΠ΄Π΅Π»Π΅ΠΉ, ΡΠ°ΠΊ ΠΈ ΡΠ°ΡΡΠ΅ΡΠΎΠ² Π² ΡΠ°ΠΌΠΊΠ°Ρ ΠΌΠΎΠ»Π΅ΠΊΡΠ»ΡΡΠ½ΠΎΠΉ Π΄ΠΈΠ½Π°ΠΌΠΈΠΊΠΈ. ΠΠ°ΡΡΠ΄Ρ Ρ ΠΎΠ΄Π½ΠΎΡΠ»ΠΎΠΉΠ½ΡΠΌΠΈ ΡΡΡΠ±ΠΊΠ°ΠΌΠΈ ΠΈΠΌΠ΅Π΅ΡΡΡ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡ ΡΠΎΠ·Π΄Π°Π²Π°ΡΡ ΠΈ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»ΠΎΠΉΠ½ΡΠ΅ ΡΡΡΠ±ΠΊΠΈ. ΠΠ»Ρ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²Π° Π½Π°Π½ΠΎΡΡΡΠ±ΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ ΡΠΏΠ΅ΡΠΈΠ°Π»ΡΠ½ΡΠ΅ ΠΊΠ°ΡΠ°Π»ΠΈΠ·Π°ΡΠΎΡΡ.