# Hướng dẫn giải đề thi đầu vào THPT Chuyên Lam Sơn - Thanh Hóa

## Bài 1 : Tính tổng

### Cách làm:

#### Subtask 1 : $L \le R \le 10 ^ 4$

Ở subtask này, ta chỉ cần duyệt for và tính tổng các số chẵn.

**Code:**

#include<bits/stdc++.h>

using namespace std;

int main(){
    
    int L , R;
    cin >> L >> R;
    
    int res = 0;
    
    for(int i = L ; i <= R ; i++)
        if(i % 2 == 0)
            res += i;
            
    cout << res << endl;
    return 0;
}

#### Subtask 2 : $L \le R \le 2 * 10 ^ 9$

Ở subtask này thì ta cần tính tổng này bằng 1 cách nhanh hơn. Ta sẽ sử dụng công thức tính tổng từ $1$ đến $n$ là $\frac{n * (n + 1)}{2}$.

Ta có ví dụ như sau:

$$2 + 4 + 6 + 8 + ... + n$$

$$= 2 * (1 + 2 + 3 + 4 + .... + n / 2)$$

Tức ta sẽ biến đổi bài toán thành tính tổng từ $\lceil \frac{L}{2} \rceil$ đến $\lfloor \frac{R}{2} \rfloor$ và nhân $2$ vào để thành tổng các số chẵn từ $L$ đến $R$.

**Lưu ý:** Ta sẽ làm tròn lên và làm tròn xuống.

**Code :**

#include<bits/stdc++.h>

using namespace std;

long long sum(int x){
    return x * (x + 1) / 2;
}

int main(){
    
    int L , R;
    cin >> L >> R;
    
    int res = 0;
    
    int X = (L + 1) / 2;
    int Y = R / 2;

    cout << 2 * (sum(Y) - sum(X - 1));
    return 0;
}

## Bài 2: Nguyên tố

### Cách làm:

#### Subtask 1: $a \le b \le 200$ , $T \le 10^3$

Ở subtask đầu tiên, ta sẽ làm với cách duyệt trâu mọi thứ. Bao gồm duyệt ước trong $O(x)$ và kiểm tra số nguyên tố trong $O(x)$.

Tổng quát lại thì độ phức tạp của ta sẽ là $\approx O(B^2 * T)$

#include<bits/stdc++.h>

using namespace std;

bool isPrime(int x){
    if(x <= 1) return false;
    for(int i = 1 ; i <= x ; i++)
        if(x % i == 0) return false;
    return true;
}

int countDiv(int x){
    int cnt = 0;
    for(int i = 1 ; i <= x; i++)
        if(x % i == 0){
            cnt++;
        }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    int numTest;
    cin >> numTest;
    
    while(numTest--){
        int a , b;
        cin >> a >> b;
        
        int cnt = 0;
        for(int i = 1 ; i <= n ; i++)
            if(isPrime(countDiv)) cnt++;
        cout << cnt << "\n";
    }
}

#### Subtask 2: $a \le b \le 2000$ , $T \le 10^3$

Ở subtask này, ta sẽ cải tiến bằng 2 bước như sau:

* Đếm số lượng ước số của $x$ trong $O(\sqrt{x})$.
* Kiểm tra số nguyên tố trong $O(\sqrt{x})$.

Có 2 bước cải tiến này, độ phức tạp của ta sẽ giảm xuống còn $O(B * \sqrt{B} * T)$, đủ để pass subtask thứ $2$.

**Code:**

#include<bits/stdc++.h>

using namespace std;

bool isPrime(int x){
    if(x <= 1) return false;
    for(int i = 1 ; i * i <= x ; i++)
        if(x % i == 0) return false;
    return true;
}

int countDiv(int x){
    int cnt = 0;
    for(int i = 1 ; i * i <= x; i++)
        if(x % i == 0){
            cnt += 2;
            if(cnt == cnt / i) cnt--;
        }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    int numTest;
    cin >> numTest;
    
    while(numTest--){
        int a , b;
        cin >> a >> b;
        
        int cnt = 0;
        for(int i = 1 ; i <= n ; i++)
            if(isPrime(countDiv)) cnt++;
        cout << cnt << "\n";
    }
}

#### Subtask 3: $a \le b \le 10^6$ , $T \le 10^5$

Ở subtask này, các giới hạn được đẩy lên rất lớn nên ta sẽ có các bước tối ưu như sau:

* Ta sẽ đếm ước cho tất cả số $x$ với $1 \le x \le 10^6$ trong $O(n * \log{n})$ thay vì duyệt từng số và đếm số lượng ước.
* Sau khi đếm số lượng ước cho mỗi số, ta sẽ chuẩn bị một mảng cộng dồn $Pref$ với $Pref_i$ là số lượng số có số ước là một số nguyên tố trong khoảng từ $1$ đến $i$.

#include<bits/stdc++.h>

using namespace std;

const int maxv = 1e6;

int cntDiv[maxv + 1]; // cntDiv[i] là số lượng ước số của i
int Pref[maxv + 1];

void prep(){
    for(int i = 1 ; i <= maxv ; i++){
        for(int j = i ; j <= maxv ; j += i)
            cntDiv[j]++;
    }
    
    Pref[1] = 0;
    for(int i = 2 ; i <= maxv ; i++){
        int t = cntDiv[i]; // t là số lượng ước của i
        if(cntDiv[t] == 2) // kiểm tra t có phải là số nguyên tố hay không
            Pref[i] = Pref[i - 1] + 1;
        else Pref[i] = Pref[i - 1];
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    prep();
    int numTest;
    cin >> numTest;
    
    while(numTest--){
        int a , b;
        cin >> a >> b;
        
        cout << Pref[b] - Pref[a - 1] << "\n";
    }
}

## Bài 3: Tìm số

### Cách làm:

#### Subtask 1: $T = 1 , a = b , N \le 2 * 10^9$

Ở subtask này, vì $a = b$ nên dãy số sinh ra sẽ chỉ là các bội số của $a$. Tức là dãy số sinh ra sẽ là:

$$a , 2*a , 3*a , 4*a, .... , i*a , .... , n*a$$

Tức lúc này, số ta cần tìm là $N * a$. Tuy nhiên, quan sát giới hạn, ta thấy $N \le 2 * 10^9 , a \le 10^5$ nên giá trị tối đa có thể nhận là $N * a = 2 * 10^{14}$ nên ta sẽ sử dụng **long long** thay vì int.

**Code:**

#include<bits/stdc++.h>

using namespace std;

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

    long long a , b , N;
    cin >> a >> b >> N;
    cout << N * a;
}

#### Subtask 2: $T = 1 , a \neq b , N \le 10^4$

Ở subtask này, ta sẽ liệt kê các số theo thứ tự tăng dần bằng cách làm việc với **Bội chung nhỏ nhất - LCM**. Ta biết, các bội số của $a$ là $i * a$ còn các bội số của $b$ là $j * b$. Tại vị trí $(i , j)$ mà $i * a = j * b$ thì đó là bội chung của $a$ và $b$. Cứ mỗi bội chung như vậy sẽ tạo ra một vòng lặp và ta có thể xác định được giá trị dựa vào vòng lặp tìm được.

**Code:**

#include<bits/stdc++.h>

using namespace std;
#define int long long

int __lcm(int a , int b){
    return a / __gcd(a , b) * b;
}

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    int numTest;
    cin >> numTest;

    long long a , b , N;
    cin >> a >> b >> N;
    
    vector<int> loop;
    int LIM = __lcm(a , b);
    
    int t = a;
    while(t < LIM){
        loop.push_back(t);
        t += a;
    }
    t = b;
    while(t < LIM){
        loop.push_back(t);
        t += b;
    }
    loop.push_back(LIM);
    
    int K = N / loop.size();
    N %= loop.size();

    if(N == 0)
        cout << LIM * K << endl;
    else cout << LIM * K + loop[N - 1] << endl;
}

#### Subtask 3: Không có ràng buộc gì thêm

- Ở subtask này, ta sẽ sử dụng kĩ thuật **tìm kiếm nhị phân**. Vậy thì làm sao để sử dụng tknp? Đầu tiên, ta sẽ có công thức để tìm số lượng số chia hết cho $X$ mà bé hơn hoặc bằng $Y$ là $\frac{X}{Y}$.

- Gọi $x$ là giá trị ta tìm nhị phân, ta có thể đếm được số lượng giá trị đã được liệt kê (gọi là $S_x$) bằng công thức:

$$S_x =\frac{x}{a} + \frac{x}{b} - \frac{x}{LCM(a , b)}$$

- Công thức trên được lý giải bằng bao hàm loại trừ.
- Có được công thức trên, việc của ta là tìm $x$ **nhỏ nhất** sao cho $S_x = N$.

**Code:**

#include<bits/stdc++.h>

using namespace std;
#define int long long

int __lcm(int a , int b){
    return a / __gcd(a , b) * b;
}

int count(int x , int a , int b){
    return x/a + x/b - x/lcm(a , b);
}

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    int numTest;
    cin >> numTest;

    while(numTest--){
        int a , b , N;
        cin >> a >> b >> N;
        
        int l = 0 , r = 1e18 , res = -1;
        
        while(l <= r){
            int mid = (l + r) / 2;
            if(count(mid , a , b) >= N){
                r = mid - 1;
                res = mid;
            }else l = mid + 1;
        }
        
        cout << res << endl;
    }
}

## Bài 4: Đảo xâu

### Cách làm

#### Subtask 1: $|S| \le 10^3$ và $m \le 10^3$.

Ở subtask này, ta chỉ cần làm trâu.

**Code :**

#include<bits/stdc++.h>

using namespace std;

string s;

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    cin >> s;
    int n = s.size();
    s = '*' + s;
    
    int mid = n / 2 + 1;
    
    int m;
    cin >> m;
    while(m--){
        int x;
        cin >> x;
        for(int i = mid ; i <= x ; i++)
            swap(s[i] , s[n - i + 1]);
    }
    
    for(int i = 1 ; i <= n ; i++)
        cout << s[i];
    cout << endl;
}

#### Subtask 2: Không có ràng buộc gì thêm

- Ở subtask này, ta sẽ sử dụng **Prefix Sum - Mảng cộng dồn** để AC.

- Gọi $f_i$ là số lần mà vị trí $i$ phải thực hiện đổi chỗ. Nếu với mỗi truy vấn ta thực hiện việc tăng $f_i$ thêm $1$ với mọi vị trí $i$ trong khoảng $i = mid \rightarrow x$. Tức, thay vì mỗi lần ta thực hiện swap với mỗi vị trí $i$ thì ta chỉ tăng $f_i$, rồi sau khi thực hiện tất cả truy vấn thì ta mới thực hiện hoán đổi nếu $f_i$ lẻ - tức là những vị trí bị hoán đổi chẵn lần không thay đổi.

Lúc này, quá trình của ta như sau:

    int m;
    cin >> m;
    while(m--){
        int x;
        cin >> x;
        for(int i = mid ; i <= x ; i++)
            f[i]++;
    }
    
    for(int i = mid ; i <= n ; i++)
        if(f[i] % 2 == 1)
            swap(s[i] , s[n - i + 1]);
    
    for(int i = 1 ; i <= n ; i++)
        cout << s[i];
    cout << endl;

Như ta thấy đoạn code:

for(int i = mid ; i <= x ; i++)
            f[i]++;

Có thể được tối ưu bằng **Prefix sum - mảng cộng dồn**. Nên lúc này, code của ta sẽ như sau:

#include<bits/stdc++.h>

using namespace std;

string s;
int f[2000005];

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    cin >> s;
    int n = s.size();
    s = '*' + s;
    
    int mid = n / 2 + 1;
    
    int m;
    cin >> m;
    while(m--){
        int x;
        cin >> x;
        f[x + 1]--;
        f[mid]++;
    }
    
    for(int i = mid ; i <= n ; i++){
        f[i] = f[i - 1] + f[i];
        if(f[i] % 2 == 1)
            swap(s[i] , s[n - i + 1]);
    }    
    
    for(int i = 1 ; i <= n ; i++)
        cout << s[i];
    cout << endl;
}