# Số học
*Anh Khá*

## Hints:
- Exponentation: nhân ấn độ (chia để trị, binary exponentation), định lý Fermat nhỏ
- Counting Divisor & Common Divisor: sàng nguyên tố. Lưu `cnt[x]` là số lượng ước của $x$.
- Sum of Divisors: chia căn đơn giản (xét 2 trường hợp) (x*y) (với mỗi số, đếm số lượng bội)
- Divisor analysis: Viết dưới dạng PT TSNT để nháp ra công thức. Với phép nhân: cần xử lý code
- Prime multiples: Bao hàm loại trừ
- Counting coprime pairs (cũng dùng mảng cnt như trên [nhưng khó hơn vì cần phải nghĩ ra công thức toán & bù trừ ntn]). $f(x)$ :số cặp chia hết cho $x$. $g(x)$: số cặp có GCD đúng bằng $x$

## B1
### Tính lũy thừa nhanh $(a^b)$
https://cp-algorithms.com/algebra/binary-exp.html#algorithm
Lưu ý một cách code ngáo:
(vì gọi đệ quy 2 lần nên độ phức tạp không đạt được $O(log_2)$)
Nộp bài https://lqdoj.edu.vn/problem/cses1095
### Fermat
Cần tính $a^{b^c} \% M$
(klq: https://lqdoj.edu.vn/problem/fermat2)
Fermat nhỏ

Có $a^{b+c} = a^b * a^c$
Cần tính $a^n, a^n = a^{n-(p-1)} a^{p-1} = a^{n-(p-1)} (\mod p)$ => Cách giảm số mũ: trừ $p-1$ vào $n$ liên tục

Hình dung phép trừ & phép chia: $a$ kẹo chia cho các bé, mỗi bé được $b$ kẹo. (phép chia lấy dư)

## B2
$O(n.log)$, harmonic series growth rate

## B3
Đếm phân phối.
Kết quả: sẽ là số $d$ lớn nhất mà có $\ge 2$ số trong $a$ chia hết cho $d$

## B4
### Áp dụng sàng để trâu
$O(n)$
###
*greek alphabet: alpha, beta, gamma, theta, sigma,*

Với mỗi số $i$, nó là ước của bao nhiêu số?
(ví dụ là $cnt$ số --> cộng vào $i \times cnt$)
ICPC bài G, miền Bắc/ Nam, năm 2022

Từ $1$ tới $n$ có bao nhiêu bội của $i$: $x = \lfloor \frac{n}{i} \rfloor$
$ix \le n \rightarrow$ hoặc $i$ hoặc $x$ sẽ $\le \sqrt{n}$
+ Trường hợp $i$ bé: chạy for theo $i$
+ Trường hợp $x$ bé: chạy for theo $x$. Có bao nhiêu số $i$ từ $1$ tới $n$ mà $\lfloor \frac{n}{i} \rfloor == x$ (chia $x$ với $x+1$). Các số $i$ này liên tiếp nhau nên lượng cộng vào là $(l+(l+1)+...+r) \times x$ (giả sử $i$ có thể nhận giá trị từ $l$ tới $r$)

## B7
Cần tính hai thứ:
+ $f(x)$ :số cặp chia hết cho $x$.
+ $g(x)$: số cặp có GCD đúng bằng $x$

Chạy $x$ từ lớn về bé để tính:
+ $g(x) = f(x) - \sum g(kx)$ (Trong $f(x)$ có những cặp có GCD bằng $x$, có những cặp có GCD bằng bội $x$ nên ta loại ra)