Сандар теориясы
Модулдук арифметика: даражага тез көтөрүү, тескери элемент жана модуль боюнча C(n,k).
Комбинаторикалык маселелердин жооптору көбүнчө астрономиялык, ошондуктан аларды «10⁹ + 7 модулу боюнча» сурашат. Калдыктар менен дээрлик сандардай эле иштесе болот:
• (a + b) % m, (a · b) % m — ар бир амалдан кийин калдык алыңыз;
• кемитүү: ((a - b) % m + m) % m — миниске кетип калбаш үчүн;
• модулдук арифметикада бөлүү ЖОК — анын ордуна тескери элементке көбөйтүү.
Даражага тез көтөрүү: a^b O(log b) убакытта — квадратка көтөрүп, көрсөткүчтүн биттерин талдайбыз. Ферманын кичине теоремасы боюнча m жай болгондо тескери элемент a⁻¹ = a^(m-2) — так ошол тез көтөрүү.
Факториалдар жана тескерилер аркылуу модуль боюнча C(n, k). Киргизиңиз: 10 3
Текшерүү: C(10, 3) = 120.
binpow талдоосу: көрсөткүч нөл болмоюнча кичи битти карайбыз (b & 1): бит орнотулган болсо — жыйынтыкка көбөйтөбүз; андан кийин негизди квадратка көтөрүп, көрсөткүчтү жылдырабыз (b >>= 1). b = 10¹⁸ үчүн — болгону 60 итерация.
Мындан ары өздөштүрүүгө арзый турган сандар теориясынын жентльмендик топтому:
• кеңейтилген Евклид алгоритми (жай ЭМЕС модуль боюнча тескери элемент);
• Эйлердин функциясы;
• калдыктар жөнүндө кытай теоремасы.
Тапшырма: n = 10¹⁸ үчүн 2^n mod (10⁹+7) эсептеңиз (binpow менен бир сап) жана C(1000, 500) айкалыштар санын модуль боюнча.
Сабакты өттүм деп белгилеңиз — 5-деңгээл аяктады!