рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо рдХреНрдпрд╛ рд╣реЛрддрд╛ рд╣реИ?
рдХрд┐рд╕реА рд╕рдВрдЦреНрдпрд╛ N рдХрд╛ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо рджреЛ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдРрд╕рд╛ рдЬреЛрдбрд╝рд╛ рд╣реИ рдЬрд┐рдирдХрд╛ рдЧреБрдгрдирдлрд▓ N рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддрд╛ рд╣реИред рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, 12 рдХреЗ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо рд╣реИрдВ \((1 \times 12)\), \((2 \times 6)\) рдФрд░ \((3 \times 4)\)ред рд╣рд░ рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХ рдХрд╛ рдХрдо рд╕реЗ рдХрдо рдПрдХ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо \((1 \times N)\) рдЬрд╝рд░реВрд░ рд╣реЛрддрд╛ рд╣реИ, рдФрд░ рдЗрди рд╕рднреА рдХреЛ рдЦреЛрдЬрдиреЗ рдкрд░ рдЙрд╕ рд╕рдВрдЦреНрдпрд╛ рдХреА рдкреВрд░реА рднрд╛рдЬрдХ рд╕рдВрд░рдЪрдирд╛ рд╕рд╛рдордиреЗ рдЖ рдЬрд╛рддреА рд╣реИ тАФ рдЬреЛ рднрд┐рдиреНрдиреЛрдВ рдХреЛ рд╕рд░рд▓ рдХрд░рдиреЗ, рдмреАрдЬрдЧрдгрд┐рддреАрдп рд╡реНрдпрдВрдЬрдХреЛрдВ рдХреЗ рдЧреБрдгрдирдЦрдВрдб рдирд┐рдХрд╛рд▓рдиреЗ рдФрд░ рдЕрднрд╛рдЬреНрдп рд╡ рднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рдмреАрдЪ рдЕрдВрддрд░ рд╕рдордЭрдиреЗ рдореЗрдВ рдмреЗрд╣рдж рдХрд╛рдо рдЖрддреА рд╣реИред
рдЗрд╕ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ
рд╕рдВрдЦреНрдпрд╛ (N) рд╡рд╛рд▓реЗ рдмреЙрдХреНрд╕ рдореЗрдВ рдХреЛрдИ рднреА рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рдбрд╛рд▓реЗрдВ рдФрд░ рд╕рдмрдорд┐рдЯ рдХрд░реЗрдВред рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдЖрдкрдХреЛ рд╣рд░ рдЕрджреНрд╡рд┐рддреАрдп рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо, рдпреБрдЧреНрдореЛрдВ рдХреА рдХреБрд▓ рдЧрд┐рдирддреА рдФрд░ рднрд╛рдЬрдХреЛрдВ рдХреА рдХреБрд▓ рд╕рдВрдЦреНрдпрд╛ рдмрддрд╛рддрд╛ рд╣реИред рдХрд┐рд╕реА рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдХрд╛ рд╕рд┐рд░реНрдлрд╝ рдПрдХ рд╣реА рдпреБрдЧреНрдо \((1 \times N)\) рдирд┐рдХрд▓рддрд╛ рд╣реИ; рдЬрдмрдХрд┐ рдХрд┐рд╕реА рдкреВрд░реНрдг рд╡рд░реНрдЧ рдХрд╛ рдПрдХ рдРрд╕рд╛ рдпреБрдЧреНрдо рдирд┐рдХрд▓рддрд╛ рд╣реИ рдЬрд┐рд╕рдореЗрдВ рджреЛрдиреЛрдВ рдЧреБрдгрдирдЦрдВрдб рдмрд░рд╛рдмрд░ рд╣реЛрддреЗ рд╣реИрдВ, рдЬреИрд╕реЗ 36 рдХреЗ рд▓рд┐рдП \((6 \times 6)\)ред
рд╕реВрддреНрд░ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛
рд╣рдо рд╣рд░ рдРрд╕реЗ рдпреБрдЧреНрдо (a, b) рдХреЛ рдЦреЛрдЬрддреЗ рд╣реИрдВ рдЬрд╣рд╛рдБ \(a \times b = \text{N}\) рд╣реЛред N рддрдХ рдХреА рд╕рднреА рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рдЬрд╛рдБрдЪрдиреЗ рдХреЗ рдмрдЬрд╛рдп, рд╣рдо рдХреЗрд╡рд▓ 1 рд╕реЗ рд▓реЗрдХрд░ N рдХреЗ рд╡рд░реНрдЧрдореВрд▓ рддрдХ рдХреА рд╕рдВрднрд╛рд╡рдирд╛рдУрдВ рдХреЛ рдкрд░рдЦрддреЗ рд╣реИрдВред
$$\{(a,\,b)\ :\ a \times b = \text{N},\ \ 1 \le a \le \sqrt{\text{N}}\}$$рдЬрдм рднреА рдХреЛрдИ a, N рдХреЛ рдкреВрд░реА рддрд░рд╣ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░рддрд╛ рд╣реИ, рддреЛ рдЙрд╕рдХрд╛ рдЬреЛрдбрд╝реАрджрд╛рд░ \(b = \text{N}/a\) рднреА рдЕрдкрдиреЗ-рдЖрдк рдПрдХ рднрд╛рдЬрдХ рдмрди рдЬрд╛рддрд╛ рд╣реИ тАФ рдпрд╛рдиреА рд╣рдо рдкреВрд░рд╛ рдпреБрдЧреНрдо рдПрдХ рд╣реА рдЪрд░рдг рдореЗрдВ рдкрдХрдбрд╝ рд▓реЗрддреЗ рд╣реИрдВред рдпрд╣реА рд╡рдЬрд╣ рд╣реИ рдХрд┐ рдпрд╣ рдЦреЛрдЬ \(O(\sqrt{\text{N}})\) рд╕рдордп рдореЗрдВ рдЪрд▓рддреА рд╣реИ рдФрд░ рдмрдбрд╝реА рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд▓рд┐рдП рднреА рддреЗрдЬрд╝ рдмрдиреА рд░рд╣рддреА рд╣реИред
рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдЙрджрд╛рд╣рд░рдг
рдорд╛рди рд▓реАрдЬрд┐рдП N = 36 рд╣реИ, рдЬрд┐рд╕рдХрд╛ рд╡рд░реНрдЧрдореВрд▓ 6 рд╣реИред 6 рддрдХ рдХреЗ рднрд╛рдЬрдХреЛрдВ рдпрд╛рдиреА \(a = 1, 2, 3, 4, 6\) рдХреЛ рдЬрд╛рдБрдЪрдиреЗ рдкрд░:
$$36 \div 1 = 36,\ \ 36 \div 2 = 18,\ \ 36 \div 3 = 12,\ \ 36 \div 4 = 9,\ \ 36 \div 6 = 6$$рдЗрд╕рд╕реЗ рдпреЗ рдпреБрдЧреНрдо рдорд┐рд▓рддреЗ рд╣реИрдВ тАФ \((1 \times 36)\), \((2 \times 18)\), \((3 \times 12)\), \((4 \times 9)\) рдФрд░ \((6 \times 6)\) тАФ рдпрд╛рдиреА рдХреБрд▓ 5 рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо рдФрд░ 9 рднрд╛рдЬрдХред
рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓
рдЕрдЧрд░ рдореИрдВ рдХреЛрдИ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдбрд╛рд▓реВрдБ рддреЛ? рдЖрдкрдХреЛ рдХреЗрд╡рд▓ рдПрдХ рд╣реА рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо \((1 \times N)\) рдорд┐рд▓реЗрдЧрд╛, рдЬреЛ рдЗрд╕ рдмрд╛рдд рдХреА рдкреБрд╖реНрдЯрд┐ рдХрд░рддрд╛ рд╣реИ рдХрд┐ рд╡рд╣ рд╕рдВрдЦреНрдпрд╛ рдЕрднрд╛рдЬреНрдп рд╣реИред
рдкреВрд░реНрдг рд╡рд░реНрдЧ рдХреЗ рдпреБрдЧреНрдореЛрдВ рдХреА рдЧрд┐рдирддреА рдЕрд▓рдЧ рдХреНрдпреЛрдВ рд╣реЛрддреА рд╣реИ? рдХрд┐рд╕реА рдкреВрд░реНрдг рд╡рд░реНрдЧ рдХрд╛ рдПрдХ рдпреБрдЧреНрдо рдРрд╕рд╛ рд╣реЛрддрд╛ рд╣реИ рдЬреИрд╕реЗ \((6 \times 6)\), рдЬрд┐рд╕рдореЗрдВ рджреЛрдиреЛрдВ рдЧреБрдгрдирдЦрдВрдб рдПрдХ рд╕рдорд╛рди рд╣реЛрддреЗ рд╣реИрдВред рдЗрд╕рд▓рд┐рдП рдпрд╣ рдПрдХ рдпреБрдЧреНрдо рдХреЗ рд░реВрдк рдореЗрдВ рдЧрд┐рдирд╛ рдЬрд╛рддрд╛ рд╣реИ, рдкрд░ рднрд╛рдЬрдХ 6 рдХреЛ рдХреБрд▓ рднрд╛рдЬрдХреЛрдВ рдореЗрдВ рд╕рд┐рд░реНрдлрд╝ рдПрдХ рдмрд╛рд░ рд╣реА рдЧрд┐рдирд╛ рдЬрд╛рддрд╛ рд╣реИред
рдХреНрдпрд╛ рдЗрд╕рдореЗрдВ рдЛрдгрд╛рддреНрдордХ рдЧреБрдгрдирдЦрдВрдб рд╢рд╛рдорд┐рд▓ рд╣реИрдВ? рдирд╣реАрдВ тАФ рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХреЗрд╡рд▓ рдзрдирд╛рддреНрдордХ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдореЛрдВ рдХреА рд╕реВрдЪреА рджреЗрддрд╛ рд╣реИ, рдЬреЛ рдкреНрд░рдЪрд▓рд┐рдд рдорд╛рдирдХ рддрд░реАрдХрд╛ рд╣реИред