Π ΡΡΠΎΠΉ Π·Π°Π΄Π°ΡΠ΅ Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠ°ΡΡ ΠΈΠΌΠΌΡΡΠ°Π±Π΅Π»ΡΠ½ΡΠΉ ΠΊΠ»Π°ΡΡ ΠΏΠΎΠ΄ Π½Π°Π·Π²Π°Π½ΠΈΠ΅ΠΌ BigInt, ΠΊΠΎΡΠΎΡΡΠΉ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΡ ΡΠΎΠ±ΠΎΠΉ Π°Π½Π°Π»ΠΎΠ³ ΠΊΠ»Π°ΡΡΠ° BigInteger. ΠΠ΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎ ΠΈΠΌΠΏΠ»Π΅ΠΌΠ΅Π½ΡΠΈΡΠΎΠ²Π°ΡΡ: ΠΠΎΠ½ΡΡΡΡΠΊΡΠΎΡ, ΠΏΡΠΈΠ½ΠΈΠΌΠ°ΡΡΠΈΠΉ String: ΡΡΡΠΎΠΊΠΎΠ²ΠΎΠ΅ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΠ΅ ΡΠΈΡΠ»Π° ΠΈ ΠΈΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·ΠΈΡΡΡΡΠΈΠΉ ΠΈΠΌ Π²Π½ΡΡΡΠ΅Π½Π½ΠΈΠΉ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΌΠ°ΡΡΠΈΠ², ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΡΠΈΠΉ ΡΠΈΡΡΡ ΡΠΈΡΠ»Π° final ArrayList digits. ΠΠ½Π°ΠΊ ΡΠΈΡΠ»Π° Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎ ΡΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ Π²ΠΎ Π²Π½ΡΡΡΠ΅Π½Π½Π΅ΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠΈΠΏΠ° boolean. ΠΠ΅ΡΠΎΠ΄ ΠΊΠ»Π°ΡΡΠ° Object: toString, ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²ΡΠ²Π°ΡΡΠΈΠΉ ΡΠΈΡΠ»ΠΎ ΠΊ ΡΡΡΠΎΠΊΠΎΠ²ΠΎΠΌΡ Π²ΠΈΠ΄Ρ. Π‘ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΡΠ°Π±ΡΠΈΡΠ½ΡΠΉ ΠΌΠ΅ΡΠΎΠ΄ valueOf, ΠΏΡΠΈΠ½ΠΈΠΌΠ°ΡΡΠΈΠΉ long ΠΈ ΡΠΎΠ·Π΄Π°ΡΡΠΈΠΉ Π½ΠΎΠ²ΡΠΉ ΠΎΠ±ΡΠ΅ΠΊΡ ΡΠΈΠΏΠ° BigInt. ΠΠ΅ΡΠΎΠ΄ add, ΠΏΡΠΈΠ½ΠΈΠΌΠ°ΡΡΠΈΠΉ Π΄ΡΡΠ³ΠΎΠΉ BigInt ΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°ΡΡΠΈΠΉ Π½ΠΎΠ²ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ, ΡΠ²Π»ΡΡΡΠ΅Π΅ΡΡ ΡΡΠΌΠΌΠΎΠΉ ΠΈΡΡ
ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΠΈΡΠ΅Π». ΠΠ΅ΡΠΎΠ΄ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΈΠ·ΠΌΠ΅Π½ΡΡΡ Π½ΠΈ ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠΈΡΠ»ΠΎ, Π½ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ΅ (ΠΊΠ»Π°ΡΡ BigInt β ΠΈΠΌΠΌΡΡΠ°Π±Π΅Π»ΡΠ½ΡΠΉ) ΠΠ΅ΡΠΎΠ΄ subtract, ΠΏΡΠΈΠ½ΠΈΠΌΠ°ΡΡΠΈΠΉ Π΄ΡΡΠ³ΠΎΠΉ BigInt ΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°ΡΡΠΈΠΉ Π½ΠΎΠ²ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ, ΡΠ²Π»ΡΡΡΠ΅Π΅ΡΡ ΡΠ°Π·Π½ΠΎΡΡΡΡ ΠΈΡΡ
ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΠΈΡΠ΅Π». ΠΠ΅ΡΠΎΠ΄ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΈΠ·ΠΌΠ΅Π½ΡΡΡ Π½ΠΈ ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠΈΡΠ»ΠΎ, Π½ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ΅ (ΠΊΠ»Π°ΡΡ BigInt β ΠΈΠΌΠΌΡΡΠ°Π±Π΅Π»ΡΠ½ΡΠΉ) ΠΠ΅ΡΠΎΠ΄ multiply, ΠΏΡΠΈΠ½ΠΈΠΌΠ°ΡΡΠΈΠΉ Π΄ΡΡΠ³ΠΎΠΉ BigInt ΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°ΡΡΠΈΠΉ Π½ΠΎΠ²ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ, ΡΠ²Π»ΡΡΡΠ΅Π΅ΡΡ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ΠΌ ΠΈΡΡ
ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΠΈΡΠ΅Π». ΠΠ΅ΡΠΎΠ΄ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΈΠ·ΠΌΠ΅Π½ΡΡΡ Π½ΠΈ ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠΈΡΠ»ΠΎ, Π½ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ΅ (ΠΊΠ»Π°ΡΡ BigInt β ΠΈΠΌΠΌΡΡΠ°Π±Π΅Π»ΡΠ½ΡΠΉ) ΠΠ΅ΡΠΎΠ΄ divide, ΠΏΡΠΈΠ½ΠΈΠΌΠ°ΡΡΠΈΠΉ Π΄ΡΡΠ³ΠΎΠΉ BigInt ΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°ΡΡΠΈΠΉ Π½ΠΎΠ²ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ, ΡΠ²Π»ΡΡΡΠ΅Π΅ΡΡ ΡΠ°ΡΡΠ½ΡΠΌ ΠΈΡΡ
ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΠΈΡΠ΅Π». ΠΠ΅ΡΠΎΠ΄ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΈΠ·ΠΌΠ΅Π½ΡΡΡ Π½ΠΈ ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠΈΡΠ»ΠΎ, Π½ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ΅ (ΠΊΠ»Π°ΡΡ BigInt β ΠΈΠΌΠΌΡΡΠ°Π±Π΅Π»ΡΠ½ΡΠΉ) ΠΠ΅ΡΠΎΠ΄ compareTo, ΠΏΡΠΈΠ½ΠΈΠΌΠ°ΡΡΠΈΠΉ Π΄ΡΡΠ³ΠΎΠΉ BigInt ΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°ΡΡΠΈΠΉ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΡΠΈΠΏΠ° int, ΡΠ°Π²Π½ΠΎΠ΅ 0, Π΅ΡΠ»ΠΈ ΡΠΈΡΠ»Π° ΡΠ°Π²Π½Ρ, 1, Π΅ΡΠ»ΠΈ ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠΈΡΠ»ΠΎ Π±ΠΎΠ»ΡΡΠ΅ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΠΈΡΠ»Π°, -1, Π΅ΡΠ»ΠΈ ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠΈΡΠ»ΠΎ ΠΌΠ΅Π½ΡΡΠ΅ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΠΈΡΠ»Π°. ΠΠ΅ΡΠΎΠ΄ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΈΠ·ΠΌΠ΅Π½ΡΡΡ Π½ΠΈ ΡΠ΅ΠΊΡΡΠ΅Π΅ ΡΠΈΡΠ»ΠΎ, Π½ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΠΎΠ΅ (ΠΊΠ»Π°ΡΡ BigInt β ΠΈΠΌΠΌΡΡΠ°Π±Π΅Π»ΡΠ½ΡΠΉ) ΠΠ°ΠΆΠ½ΠΎ Π ΡΡΠΎΠΉ Π·Π°Π΄Π°ΡΠ΅ Π½Π΅ Π½ΡΠΆΠ½ΠΎ ΠΏΠΈΡΠ°ΡΡ ΡΡΠ½ΠΊΡΠΈΡ main. ΠΡΠ»ΠΈ ΠΏΠΎΡΡΠ΅Π±ΡΠ΅ΡΡΡ, ΠΌΠΎΠΆΠ΅ΡΠ΅ ΡΠ΄Π΅Π»Π°ΡΡ import Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΡΡ
ΠΏΠ°ΠΊΠ΅ΡΠΎΠ². ΠΡΠ»ΠΈ Π²Ρ ΠΎΡΠΈΠ±Π΅ΡΠ΅ΡΡ Π² ΡΠΈΠ³Π½Π°ΡΡΡΠ΅ ΠΊΠ°ΠΊΠΎΠ³ΠΎ-ΡΠΎ ΠΌΠ΅ΡΠΎΠ΄Π°, Π»ΠΈΠ±ΠΎ Π·Π°Π±ΡΠ΄Π΅ΡΠ΅ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ ΠΊΠ°ΠΊΠΎΠΉ-ΡΠΎ ΠΌΠ΅ΡΠΎΠ΄, ΡΠΎ ΡΠ΅ΡΡΠ΅Ρ ΡΠΏΠ°Π΄Π΅Ρ Ρ ΠΎΡΠΈΠ±ΠΊΠΎΠΉ ΠΊΠΎΠΌΠΏΠΈΠ»ΡΡΠΈΠΈ, ΠΏΠΎΡΡΠΎΠΌΡ Π±ΡΠ΄ΡΡΠ΅ Π²Π½ΠΈΠΌΠ°ΡΠ΅Π»ΡΠ½Ρ! ΠΡΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠΈ Π·Π°Π΄Π°ΡΠΈ, Π΅ΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎ, Π·Π°ΠΏΡΠ΅ΡΠ°Π΅ΡΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΊΠ»Π°ΡΡ BigInteger. ΠΡΠΈΠΌΠ΅Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ ΠΊΠ»Π°ΡΡΠ° BigInt (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π² ΡΡΠ½ΠΊΡΠΈΠΈ main): final BigInt a = BigInt.valueOf(123).multiply(BigInt.valueOf(44)).add(BigInt.valueOf(3)); final BigInt b = BigInt.valueOf(777).divide(BigInt.valueOf(7)).subtract(BigInt.valueOf(3)); final int c = a.compareTo(b); System.out.println(a + (c == 0 ? “ == “ : (c == -1 ? “ < “ : “ > “)) + b); Π’Π°ΠΊΠΎΠΉ ΠΊΠΎΠ΄ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π²ΡΠ²Π΅ΡΡΠΈ: 5415 > 108 Codestyle [2 Π±Π°Π»Π»Π°]: ΡΡΠΈΠ»Ρ ΠΊΠΎΠ΄Π° Π΄ΠΎΠ»ΠΆΠ΅Π½ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΎΠ²Π°ΡΡ ΡΡΠ°Π½Π΄Π°ΡΡΠ°ΠΌ, ΠΎΠΏΠΈΡΠ°Π½Π½ΡΠΌ Π² ΡΡΠΎΠΌ Π΄ΠΎΠΊΡΠΌΠ΅Π½ΡΠ΅. Π’Π°ΠΊΠΆΠ΅, ΠΏΡΠΈΠΊΠ»Π°Π΄ΡΠ²Π°Ρ ΠΏΠΎΠ»Π΅Π·Π½ΡΡ ΠΈ ΠΏΡΠΎΡΡΡΡ ΡΡΠ°ΡΡΡ ΠΠΎΠ³ΠΈΠΊΠ° ΠΈ ΠΏΠΎΠ½ΡΡΠ½ΠΎΡΡΡ ΠΊΠΎΠ΄Π°, ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΡΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ [5 Π±Π°Π»Π»ΠΎΠ²]: Π²Π°Ρ ΠΊΠΎΠ΄ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±ΡΡΡ Π»ΠΎΠ³ΠΈΡΠ΅Π½, ΡΠ°Π·Π΄Π΅Π»Π΅Π½ Π½Π° ΠΏΠΎΠ½ΡΡΠ½ΡΠ΅ ΡΡΡΡΠΊΡΡΡΠ½ΡΠ΅ Π΅Π΄ΠΈΠ½ΠΈΡΡ, ΠΊΠΎΠ΄ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΡΠΈΡΠ°ΡΡΡΡ ΠΊΠ°ΠΊ ΡΠ΅ΠΊΡΡ. ΠΡΠΈ Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎΡΡΠΈ, Π½Π΅ ΡΡΠ΅ΡΠ½ΡΠΉΡΠ΅ΡΡ Π΄ΠΎΠ±Π°Π²Π»ΡΡΡ ΠΏΠΎΡΡΠ½ΡΡΡΠΈΠ΅ ΠΊΠΎΠΌΠΌΠ΅Π½ΡΠ°ΡΠΈΠΈ. ΠΠΎΠ΄ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±ΡΡΡ Π»Π°ΠΊΠΎΠ½ΠΈΡΠ΅Π½: Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π΅ΡΠ»ΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠ±ΠΎΠΉΡΠΈΡΡ ΡΠ΅ΡΠ½Π°ΡΠ½ΡΠΌ ΠΎΠΏΠ΅ΡΠ°ΡΠΎΡΠΎΠΌ, Π²ΠΌΠ΅ΡΡΠΎ Π²Π΅ΡΠ²Π»Π΅Π½ΠΈΡ, Π»ΡΡΡΠ΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΈΠΌΠ΅Π½Π½ΠΎ ΡΠ΅ΡΠ½Π°ΡΠ½ΡΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΎΡ. Π’Π°ΠΊΠΆΠ΅ Π² ΡΡΠΎΠΌ ΠΊΡΠΈΡΠ΅ΡΠΈΠΈ ΠΎΡΠ΅Π½ΠΈΠ²Π°Π΅ΡΡΡ ΡΠ΄Π°ΡΠ½ΠΎΡΡΡ Π½Π°Π·ΡΠ²Π°Π½ΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ
. ΠΠΎΡΡΠ΅ΠΊΡΠ½ΠΎΡΡΡ ΠΊΠΎΠ΄Π° [4 Π±Π°Π»Π»Π°]: Π²Π°Ρ ΠΊΠΎΠ΄ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΡΠ°Π±ΠΎΡΠ°ΡΡ Π½Π΅ ΡΠΎΠ»ΡΠΊΠΎ Π½Π° ΡΠ΅ΡΡΠΎΠ²ΡΡ
ΠΏΡΠΈΠΌΠ΅ΡΠ°Ρ
, Π½ΠΎ ΠΈ Π² Π»ΡΠ±ΡΡ
ΠΎΡΡΠ°Π»ΡΠ½ΡΡ
ΡΠ»ΡΡΠ°ΡΡ
, ΡΠΎ Π΅ΡΡΡ Π²ΡΠ΅ ΠΊΡΠ°ΠΉΠ½ΠΈΠ΅ ΡΠ»ΡΡΠ°ΠΈ Π΄ΠΎΠ»ΠΆΠ½Ρ Π±ΡΡΡ ΡΡΡΠ΅Π½Ρ. ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΡΡΡ [1 Π±Π°Π»Π»]: ΠΌΠ΅ΡΠΎΠ΄Ρ multiply ΠΈ divide Π΄ΠΎΠ»ΠΆΠ½Ρ ΡΠ°Π±ΠΎΡΠ°ΡΡ Π·Π° O(N^2), ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΈ ΠΊΠΎΠ½ΡΡΡΡΠΊΡΠΎΡ β Π·Π° O(N), Π³Π΄Π΅ β ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠΈΡΡ Π² Π΄Π΅ΡΡΡΠΈΡΠ½ΠΎΠΉ Π·Π°ΠΏΠΈΡΠΈ ΡΠΈΡΠ»Π°.