# Modulli arifmetika va binar daraja

## Modulli arifmetika

**Masala**
$a$ va $b$ sonlari ko'paytmasini toping $a, b \leq 10^{18}$

Masala juda ham oson ko'rinadi, ammo unda bir kamchilik bor. $a$ va $b$ sonlarini eng katta qiymatlarida (ya'ni $10^{18}$) ko'paytma qiymati $10^{36}$ bo'lib ketadi. Ammo bunday katta sonni kompyuter xotirasida saqlab bo'lmaydi(oddiy tipli o'zgaruvchilar bilan). Shuning uchun ham bu kabi masalalarda masala natijasini qandaydir katta butun son, masalan $10^9+7$ ga bo'lgandagi qoldiqni topish so'raladi. Bu esa javobni to'g'riligini tekshirishga katta qulaylik beradi.

Javobni qoldiq bilan topish u qadar qiyin emas, oddiy yechimga bir qancha o'zgarishlar kiritish kifoya.

Modulli arifmetikani asosiy $3$ ta formulasi bor:

- $(a + b)\ mod\ m = ((a\ mod\ m) + (b\ mod\ m))\ mod\ m$
- $(a - b)\ mod\ m = ((a\ mod\ m) - (b\ mod\ m)\ + m)\ mod\ m$
- $(a * b)\ mod\ m = ((a\ mod\ m) * (b\ mod\ m))\ mod\ m$

Bu yerda $a\ mod\ b$ - $a$ sonini $b$ ga bo'lgandagi qoldiqni bildiradi.

Umuman olganda, ikki son ustida qandaydir amal bajarishdan oldin, ularni o'zidan alohida qoldiq olib, so'ngra umumiy natijadan qoldiq olish mumkin. Bu esa bizga juda katta qulaylik beradi. Yuqoridagi misolni o'zini oladigan bo'lsak, qiymati $10^{18}$ bo'lgan sonni ko'paytirishdan oldin $m=10^9+7$ soniga qoldiq olsak, a ni qiymati $10^9+6$ dan oshmasligini kafolatlay olamiz.

Yuqoridagi masalani yechilishi

long long mod = 1000000007ll;
long long a, b;
cin >> a >> b;
cout << ((a % mod) * (b % mod)) % mod;

**Masala**
$n!$ ni $10^9+7$ ga bo'lgandagi qoldiqni toping.

int n;
cin >> n;

long long ans = 1, mod = 1000000007ll;

for(int i = 1; i <= n; i ++)
    ans = (ans * i) % mod;
    
cout << ans << '\n';

:::info
Ya'ni $ans$ ga har bir $i$ ni ko'paytirgandan so'ng qoldiq olamiz.
:::

:pushpin: Masalalar
- [https://cses.fi/problemset/task/1617](https://cses.fi/problemset/task/1617)

## Darajaga ko'tarishning Binar usuli

**Masala**
$a$ sonini $n$-darajasini $10^9+7$ ga bo'lgandagi qoldiqni toping.

Bu masalani yechishni eng oddiy usuli, for sikli yordamida javobni topish:

long long a, n, mod = 1000000007ll;
cin >> a >> n;

ll ans = 1;

for(int i = 1; i <= n; i ++)
    ans = (ans * a) % mod;

cout << ans << '\n';

Bu yechim $n <= 10^7$ bo'lgandagina ishlaydi xolos. $n$ ni kattaroq qiymatlari uchun ishlash uchun *samaraliroq* algoritm kerak bo'ladi.

:::danger
:exclamation: Biror sonni darajaga ko'tarish deganda ko'pchilikni hayoliga C++dagi $pow$ funksiyasi keladi. Amalda $pow$ dan foydalanish tavsiya etilmaydi, chuni bu funksiya haqiqiy sonlar bilan ishlaydi, bu esa aniqlikka ta'sir ko'rsatadi. $pow$ o'rniga qo'lda alohida funksiya tuzib ishlatkan ma'qulroq.
:::

### Binary exponentation

Yuqoridagi yechimda $a^n$ ni $n$ ta $a$ ko'paytmasi ko'rinishida tasvirlab hisobladik, ya'ni:
$$a^n=a \cdot a \cdot\ ...\ \cdot a$$

Binar darajada esa $n$ ikkini darajalari yig'indisi ko'rinishida ko'rinishida ifodalab olinadi, ya'ni:
$$3^{11}=3^{1011_2}=3^8*3^2*3^1$$
$n=11$ ni ikkini darajasi ko'rinishida yozish uchun, undagi har bir *yoniq* bitga mos $2$ ni darajalarini qo'shib chiqish kifoya, ya'ni:
- $1011_2$ ni chapdan $0$-biti $1$, shunga summaga $2^0=1$ ni qo'shamiz
- $1011_2$ ni chapdan $1$-biti $1$, shunga summaga $2^1=2$ ni qo'shamiz
- $1011_2$ ni chapdan $3$-biti $1$, shunga summaga $2^3=8$ ni qo'shamiz

:::info
:bulb: Bitlar har doim **o'ngdan chapga qarab** $0$ dan boshlab indekslanadi. Eng o'ngdagi bit $0$-bit, undan chaproqdagisi $1$-bit, $2$-bit va hokazo. Ya'ni ikkilikdagi $1011101_2$ soni quyidagicha indekslanadi:
$$indeks \ \ \ 6\ 5\ 4\ 3\ 2\ 1\ 0$$

$$bitlar \ \ \ \ \ 1\ 0\ 1\ 1\ 1\ 0\ 1$$
:::

Demak, javobni topish uchun $n$ ni ikkilik ko'rinishida o'ngdan chapga qarab borib, agar o'sha indeksdagi bit $1$ bo'lsa, javobga shu indeks uchun mos ikkini darajasini ko'paytiramiz.

long long a, n, mod = 1000000007ll;
cin >> a >> n;

long long ans = 1;
while(n > 0)
{
    if(n % 2 == 1)
        ans = (ans * a) % mod;

    a = (a * a) % mod;
    n /= 2;
}

cout << ans << '\n';

Yuqoridagi kodda o'ngdan birinchi bitni $1$ ekanligini tekshirish uchun uni toqligini tekshirdik. Agar n toq bo'lsa uni o'ngdagi birinchi biti har doim $1$ bo'ladi, shuning uchun javobga $a$ ni ko'paytirdik. $a$ ni qiymati esa hisoblashlar davomida boshlang'ich $a$ ning darajalari $a^1, a^2, a^4, a^8,...$ kabi qiymatlarga teng bo'ladi. Har bir qadamda $n$ ni ikkiga bo'lish navbatdagi(chapdagi) bitga o'tish imkonini beradi.

:pushpin: Masalalar
- https://cses.fi/problemset/task/1095

:::success
:bulb: Har bir algoritmni qanday ishlashini tushunish juda ham muhim bo'lishiga qaramay, ba'zida uni tushunmay qolsangiz, uni yechimini tushunib olib, kerak bo'lsa yodlab olib ishlatib ketish mumkin. Keyinchalik tajribaliroq bo'lgandan so'ng ushbu algoritmni chuqurroq o'rganib olsa bo'ladi.
:::