---
title
Toán và số học - Lời giải
---

Toán và số học - Lời giải
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

Trước khi bắt đầu bài viết, với mỗi bài, các bạn có thể nhấp vào bài 1, 2, 3 để xem link nộp bài chấm thử độ chính xác bài làm của mình (trong bài 3 thì các bài cần thêm `freopen` và sắp xếp lại các giá trị) . Chúc các bạn đọc bài vui vẻ!

# [Bài 1](https://oj.vnoi.info/problem/maxnum)
**Đề bài:** Cho 2 số nguyên dương $N, P$. Tìm số nguyên không âm $M$ lớn nhất sao cho $P^M$ là ước của $N!$ (ký hiệu $x!$ là $x$ **giai thừa** hay bằng $1 \times 2 \times 3 \times... \times x$).
**Dữ liệu đề bài đảm bảo luôn tìm được nghiệm**.

**INPUT:**
- 1 dòng duy nhất chứa là hai số nguyên dương $N$ và $P$ $(\leq 30.000)$.

**OUTPUT:**
- 1 dòng duy nhất là số $M$ lớn nhất thỏa điều kiện.

**VD:**
| INPUT | OUTPUT |
| -------- | -------- |
| 7 3 | 2 |

- Giải thích : $7!=1 \times 2 \times 3 ... \times 7=5.040$, $5.040$ chia hết cho $P^2=9$ . Giả sử $M=3$ thì $5.040$ không chia hết cho $P^3=27$.

**Lời giải**
* Để giải bài toán này chúng ta thấy rằng, không thể tìm được $N!$ vì kết quả của $N!$ sẽ lớn hơn rất nhiều so với giới hạn số tự nhiên trong C++ (khoảng $10^{18}$). Do đó, ta cần phân tích $N!$ ra thừa số nguyên tố để xử lí.
* Thêm vào đó, để hai số chia hết cho nhau, thì số chia hết phải có tích ước số nguyên tố bao gồm tích ước số nguyên tố của số bị chia. Ví dụ: $12$ chia hết cho $6$ vì $12$ bao gồm tích ước số nguyên tố của $6$ là $2 * 3$.
* Ví dụ: 12 có tích ước nguyên tố là $2^{2}$ * $3$ nên $12^{2}$ sẽ có tích nguyên tố là $2^{4}$ * $3^{2}$. Do đó, số lượng của một số nguyên tố trong tích nguyên tố sẽ được tăng lên đúng với số lần nhân.
* Vì thế, ta sẽ đếm số lần xuất hiện của từng số nguyên tố tạo nên tích của $N!$ và của $P$, đáp án của bài sẽ là số nhỏ nhất giữa thương của các số nguyên tố mà $P$ có so với $N!$ có.
* Để phân tích số ra thừa số nguyên tố, ta có thể sử dụng sàng số nguyên tố để giảm độ phức tạp xuống $O(\log n)$
:::spoiler **Code mẫu:**

#include <bits/stdc++.h>  
using namespace std;

const int N = 100005;

int prime[N], n, p, d1[N], d2[N];

void sieve() {  // sàng số nguyên tố, gắn những bội của i là i
    int LIM = max(n, p);
    for(int i = 2; i <= LIM; ++i) {
        prime[i] = i;
    }
    
    for(int i = 2; i * i <= LIM; ++i) if(prime[i]==i){
        for(int j = i * i; j <= LIM; j += i){
            prime[j]=i;
        }
    }
}

void factorize(int x,int d[]) { 
    // Phân tích thừa số nguyên tố
    // int d[] có nghĩa là tụi mình truyền tham biến vào mảng d[]
    while (x > 1){
       d[prime[x]] += 1;
       x /= prime[x];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> p;
    if(n == 1 && p == 1){ // Trường hợp đặc biệt vì sàng sử dụng trong code này chạy từ 2
        cout << 1;
        return 0;
    }
    
    sieve();
    for (int i = 2; i <= n; ++i){  // Phân tích thừa số nguyên tố của N!
        factorize(i,d1); // Phân tích 2, 3, 4, 5, ..., N
    }
    
    factorize(p,d2);  // Phân tích thừa số nguyên tố của số P
    int ans=INT_MAX;
    for (int i = 2; i <= p; ++i){  // Tìm số nhỏ nhất giữa thương của các số nguyên tố mà $P$ có so với $N!$ có
        if (d1[i] > 0 && d2[i] > 0){
            ans = min(ans, d1[i] / d2[i]);
        }
    }
    
    if(ans == INT_MAX){  // Nếu N! không thể chia hết cho số P thì ta cho M là 0 để P mũ M là 1
        cout << 0;
        return 0;
    }
    cout << ans;
    return 0;
}

:::
# [Bài 2](https://oj.vnoi.info/problem/nkabd)
**Đề bài:** Một số nguyên dương được gọi là **phong phú** nếu tổng các ước số không kể chính nó lớn hơn số đó. Ví dụ $12$ có tổng ước số không kể chính nó là $1+2+3+4+6=16>12$. Do đó $12$ là một số phong phú. Đếm xem trong đoạn $[L, R]$ có bao nhiêu số phong phú.

**INPUT:**
- 1 dòng duy nhất gồm hai số $L, R$ $(1 \leq L \leq R \leq 10^6)$.

**OUTPUT**
- 1 dòng duy nhất gồm số lượng số phong phú trong đoạn $[L, R]$.

**VD:**
| INPUT | OUTPUT |
| -------- | -------- |
| 1 50 | 9 |

- Giải thích : các số phong phú trong đoạn $[1, 50]$ là $12, 18, 20, 24, 30, 36, 40, 42, 48$.

**Lời giải**
- Bài này chúng ta thấy mối quan hệ giữa việc đếm số ước của một số $x$ bất kì và tổng ước số
- Với dữ kiện của đề bài là tổng các ước số $x$ khác chính $x$ tương đương việc lấy tổng các ước của $x$ rồi trừ cho $x$
- Ở bài [Toán và số học](https://hackmd.io/EomwVdxnT663LQaC80_Zig#B%C3%A0i-to%C3%A1n-1--T%C3%ADnh-s%E1%BB%91-%C6%B0%E1%BB%9Bc-s%E1%BB%91-c%E1%BB%A7a-nhi%E1%BB%81u-s%E1%BB%91-trong-m%E1%BB%99t-%C4%91o%E1%BA%A1n) trong phần tính số ước số của một số, chúng ta có thể biến đổi lại code một tí. Gọi $\text{sum_divisor}_{x}$ là tổng các ước **tính cả chính nó** của $x$
- Thay vì với ở code trước đó, ta cộng $1$ lên $cnt_{i \times i}$ và cộng $2$ với $cnt_{k \times i}$ $(k>i)$, ta sẽ cộng $i$ với $\text{sum_divisor}_{i \times i}$ và cộng $i+k$ với $\text{sum_divisor}_{k \times i}$
- Sau khi sàng xong, ta chỉ việc trừ mỗi $\text{sum_divisor}_i$ cho $i$ và đếm số lượng số thỏa mãn.
- Độ phức tạp : $O(n \log \log n)$
:::spoiler **Code mẫu:**

#include<bits/stdc++.h>

using namespace std;

const int N = 100005;
//ở đây tụi mình ghi trong đề giới hạn 10^6 để tránh việc các bạn tính từng
//số x bằng thuật O(sqrt(x)) và trong link submit giới hạn chỉ là 10^5

long long sum_divisor[N];
//mảng lưu lại tổng các giá trị các ước khác chính nó
//lưu ý là có thể tổng vượt qua giá trị lớn nhất của kiểu int nên để an toàn tụi mình
//sử dụng long long

void sieve(int n){ //
  for(int i = 1; i * i <= n; ++i){
    sum_divisor[i * i] += i;
    for(int j=(i+1) * i; j <= n; j += i){
      sum_divisor[j] += i + (j/i); // ở đây, k chính là j/i
    }
  }
  //lưu ý, ở đây mình phải trừ đi i vì thuật ban đầu của mình tính
  // tổng ước tính cả chính nó
  for(int i = 1; i <= n; ++i){
    sum_divisor[i] -= i;
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL); cout.tie(NULL);

  int L, R; cin >> L >> R;
  sieve(R); //sàng từ 1 tới R

  int ans = 0;
  //kiểm tra và đếm thông thường
  for(int i = L; i <= R; ++i){
    if(sum_divisor[i] > i){
      ans += 1;
    }
  }
  cout << ans;

  return 0;
}

:::
# [Bài 3](http://lhpoj.lehongphong.edu.vn/problem/ts2022_modulo)
**Đề bài:** Cho một dãy số nguyên không âm $a$ gồm $N$ phần tử (trong đó có ít nhất 2 giá trị phân biệt). Tìm tất cả số nguyên dương $M$ sao cho $a_1 \ \text{mod} \ M = a_2 \ \text{mod} \ M = a_3 \ \text{mod} \ M = ... = a_N \ \text{mod} \ M$

**INPUT:**
- Dòng đầu là số nguyên dương $N$ $(2 \leq N \leq 10^6)$
- Dòng tiếp theo là $N$ số nguyên không âm $a_i$ $(\leq 10^9)$

**OUTPUT:**
- Dòng đầu tiên là số lượng số $M$ thỏa mãn
- Dòng tiếp theo là các số $M$ thỏa mãn theo thứ tự bất kì

**VD:**
| INPUT | OUTPUT |
| -------- | -------- |
| 5 | 2 |
| 4 13 16 10 7 | 1 3|

- Giải thích:
- Với $M=1$, ta có $N$ số trong test đề dư $0$ nên $M=1$ thỏa điều kiện
- Với $M=3$, ta có $N$ số trong test đề dư $1$ nên $M=3$ thỏa điều kiện
- Giả sử $M=5$, ta có $4 \ \text{mod} \ 5 = 4$, $13 \ \text{mod} \ 5 = 3$, $16 \ \text{mod} \ 5 = 1$, $10 \ \text{mod} \ 5 = 0$, $7 \ \text{mod} \ 5 = 2$ gồm nhiều giá trị khác nhau nên $M=2$ không thỏa mãn

**Lời giải**

- Phát biểu lại đề bài, ta có :
+ $a_1 \equiv a_2 \ (\text{mod} \ M)$
+ $a_2 \equiv a_3 \ (\text{mod} \ M)$
+ $a_3 \equiv a_4 \ (\text{mod} \ M)$
+ ...
+ $a_{N-1} \equiv a_N \ (\text{mod} \ M)$

- Từ đây suy ra theo tính chất $6$ trong phần [Đồng dư thức](https://hackmd.io/EomwVdxnT663LQaC80_Zig?view#%C4%90%E1%BB%93ng-d%C6%B0-th%E1%BB%A9c) :
+ $a_1 \equiv a_2 \ (\text{mod} \ M) ⇔ (a_1-a_2) \equiv 0 \ (\text{mod} \ M)$
+ $a_2 \equiv a_3 \ (\text{mod} \ M) ⇔ (a_2-a_3) \equiv 0 \ (\text{mod} \ M)$
+ $a_3 \equiv a_4 \ (\text{mod} \ M) ⇔ (a_3-a_4) \equiv 0 \ (\text{mod} \ M)$
+ ...
+ $a_{N-1} \equiv a_N \ (\text{mod} \ M) ⇔ (a_{N-1}-a_N) \equiv 0 \ (\text{mod} \ M)$

- Điều này đồng nghĩa với việc các số $M$ ta cần tìm chính là ước chung của :
+ $|a_1-a_2|, |a_2-a_3|, |a_3-a_4|, ..., |a_{N-1}-a_N|$

- Bài toán của ta đã trở thành tìm các số là ước chung của hiệu mỗi cặp phần tử liên tiếp $|a_i-a_{i+1}|$. Để giải quyết phần này, ta có thể có nhiều cách khác nhau nhưng ở đây tụi mình chỉ sẽ trình bày 1 trong những cách trên.

- **Hướng giải quyết** : Ta thấy khi ta có số nguyên dương $T$ là **ước chung lớn nhất** của hiệu các cặp phần tử liên tiếp, nó đồng nghĩa với việc các **đáp án** còn lại cũng chính là một trong những ước của $T$. Vì vậy khi ta có được **ước chung lớn nhất**, ta sẽ giải được bài toán.

- Độ phức tạp : $O(n \times \log n)$

:::spoiler **Code mẫu**

#include<bits/stdc++.h>

using namespace std;

const int N = 1000005;

int n, a[N];

int main(){
  //3 hàm tăng tốc độ nhập/xuất
  ios_base::sync_with_stdio(0);
  cin.tie(NULL); cout.tie(NULL);

  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }

  int T = abs(a[1] - a[2]); //đặt T ban đầu là hiệu của a[1] và a[2]
  for(int i = 2; i < n; ++i){
    //tính ước chung lớn nhất giữa T và hiệu của a[i] và a[i+1]
    T = __gcd(T, abs(a[i] - a[i+1]));
  }

  //mảng vector chứa đáp án của chúng ta
  vector<int> res;
  for(int i = 1; i * i <= T; ++i){
    if(T % i == 0){
      res.push_back(i);
      if(i != (T/i)) res.push_back(T / i);
      //phần kiểm tra, nếu T là số chính phương thì đáp án sqrt(T) sẽ bị lặp 2 lần
    }
  }

  cout << res.size() << '\n'; //số lượng số nguyên dương M thỏa mãn
  for(int i = 0; i < res.size(); ++i){
    cout << res[i] << ' '; //các số M
  }

  return 0;
}