## Hint 1:
Cần đếm xem `i` xuất hiện trong bao nhiêu gcd của các tập hợp.
---
## Hint 2:
Sử dụng bao hàm loại trừ như bài marisaoj 427.
Cụ thể xét `i` từ `1e6` về `1`, ta tính `f[i]` là số tập con thỏa `gcd = i`.
Với mỗi `i`, xét tìm các **bội của `i`** tồn tại trong mảng. Lúc này ta tính được **số tập hợp thỏa gcd là bội của `i`**.
Bây giờ ta cần phải trừ đi các tập hợp có `gcd` là bội của `i` nhưng mà **khác `i`**, ta sẽ trừ các `f[i*z]` với `z > 1`.
**Vì sao nó đúng?**
Các `f[i*z]` là số tập con có `gcd = i*z` nên hiển nhiên **giao của chúng là rỗng**.
Vì thế ta có nhận xét sau:
**Số tập thỏa gcd là bội của `i` = tổng các `f[i*z]` (với `z > 0`)**
=> Để tính `f[i]`, ta sẽ bù trừ lại:
```
f[i] = (2^cnt[i] - 1) - ∑ f[i*z] (z > 1)
```
---
## Hint 3:
Ta có `f[i]` và cần tính `i ^ f[i]`, ta có thể thấy `f[i]` là rất lớn đến `2^1e6`.
Không thể để `f[i] mod 1e9+7` vì:
```
a^x mod 1e9+7 != a^(x mod 1e9+7) mod 1e9+7
```
Nhưng ta có thể mod một số khác, đó chính là `1e9+6`, cụ thể:
```
a^x mod 1e9+7 = a^(x mod 1e9+6) mod 1e9+7
```
**Chứng minh:**
Theo định lý Fermat nhỏ, nếu `m` là số nguyên tố:
```
a^(m-1) ≡ 1 (mod m)
⇒ a^x ≡ a^(x mod (m-1)) (mod m)
```
---
## Source code:
https://ideone.com/22W713
RussVN123
Created at
1 likes