# Chữa đề Tuyển sinh 10 Tỉnh Quảng Bình môn Tin.
Người viết: Nguyễn Khắc Trung, Võ Ngọc Sinh.
Chấm thử bằng bộ test không chính thức [tại đây](https://ltoj.edu.vn/contest/qbts102425)
Do bài viết được viết trong thời gian rất ngắn nên nếu có sai sót gì về sol hay test, hãy liên hệ với tụi mình nhe :>.
## Bài 1 - MOD
Ta tính tích tất cả các số đoạn $[a..b]$, tuy nhiên ta phải mod cho $m$ trong quá trình nhân do kết quả của phép nhân tăng rất nhanh($a=1,b=21$ là đã đủ tràn kiểu dữ liệu long long).
### Code mẫu

long long a,b,m,res=1;cin>>a>>b>>m;
for(int i=a;i<=b;i++) res*=i,res%=m;
cout<<res;

## Bài 2 - LENGTH
Đối với các thí sinh sử dụng C++, thì đây coi như là 2,5 điểm free. Ta có thể nhập từng từ một nên ta chỉ cần nhập từ đó rồi in ra độ dài của từ đó.
### Code mẫu C++

string str;
while(cin>>str) cout<<str.size()<<" ";

Đối với ngôn ngữ khác, ta sẽ duyệt qua từng ký tự, nếu ký tự đang xét là ký tự rỗng, ta sẽ in ra những ký tự khác rỗng đã đếm trước đó, còn không thì ta tăng biến đếm lên $1$.

### Code mẫu Python

str=input()
cnt=0
last_chr=' '
for chr in str: 
    if (chr==' ' and last_chr!=' '): 
        print(cnt,end=" ")
        cnt=0
    else: 
        cnt+=1
        last_chr=chr
print(cnt)

## Bài 3 - VIDEO
Tóm tắt đề: Cho dãy số nguyên dương $a$ có $n$ phần tử,tìm cặp số $(i,j)(1 \leq i \leq j \leq n)$ sao cho $(j-i+1)$ bé nhất và tổng các phần tử từ $i$ đến $j$ lớn hơn hoặc bằng $s$.
### Subtask 1
Duyệt tất cả các cặp $(i,j)$ rồi kiểm tra xem tổng các phần tử đoạn $[i..j]$ có lớn hơn hoặc bằng tổng $s$ hay không.
#### Code mẫu C++

int res=n;
for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
        {
            long long sum=0;
            for(int k=i;k<=j;k++) sum+=a[k];
            if (sum>=s) res=min(res,j-i+1);
        }

Độ phức tạp thời gian : $O(N^3)$
### Subtask 2
Thay vì phải mất một vòng lặp cho việc tính tổng, ta có thể tính nhanh tổng từ $i$ đến $j$ bằng mảng tiền tố trong $O(1)$.
#### Code mẫu C++

int res=n;
for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
        if (a[j]-a[i-1]>=s) res=min(res,j-i+1);

Độ phức tạp thời gian : $O(N^2)$
### Subtask 3
Ta thấy mảng tiền tố là một mảng tăng dần nên ta có thể sử dụng Tìm kiếm nhị phân hay Hai con trỏ.
#### Tìm kiếm nhị phân
Với mỗi $i$, ta chặt nhị phân tìm $j$ bé nhất sao cho tổng các phần tử đoạn $[i..j]$ lớn hơn hoặc bằng $s$.
##### Code mẫu C++

int res=n;
for(int i=1;i<=n;i++){
    int l=i,r=n,k=-1;
    while (l<=r)
    {
        int c=(l+r)>>1;
        if (a[c]-a[i-1]>=s) k=c,r=c-1;
        else l=c+1;
    }
    if (k!=-1) res=min(res,k-i+1);
}

Độ phức tạp thời gian : $O(Nlog(N))$
#### Hai con trỏ
Ta sẽ duy trì một biến $r$ luôn luôn thỏa mãn điều kiện tổng đoạn $[l..r]$ lớn hơn hoặc bằng $s$ và $r$ luôn bé nhất.

##### Code mẫu C++

int r=1;
for(int l=1;l<=n;l++)
{
    while (r<n and a[r]-a[l-1]<s) r++;
    if (a[r]-a[l-1]<s) break;
    res=min(res,r-l+1);
}

Độ phức tạp thời gian : $O(N)$
## Bài 4 - ROBOT
Tóm tắt đề: Cho hai số nguyên dương $x$ và $y$, đếm số lần tăng $y$ lên $1$ đơn vị để ước chung lớn nhất của $x$ và $y$ khác $1$.
### Subtask 1
Cứ tăng $y$ đến khi nào $gcd(x,y)\neq 1$ thì dừng lại. Kiểm tra gcd bằng cách sử dụng một vòng lặp.
#### Code mẫu C++

int gcd(int x,int y,int res=1){
    for(int i=2;i<=min(x,y);i++)
        if (x%i==0 and y%i==0) res=i;
    return res;
}
int t;cin>>t;
while (t--){
    int x,y,cnt=0;cin>>x>>y;
    while (gcd(x,y)==1) y++,cnt++;
    cout<<cnt<<"\n";
}

Độ phức tạp thời gian $O(max(x,y)\min(x,y))$
### Subtask 2
Sử dụng thuật toán Euclid để tính GCD, từ đó giảm độ phức tạp thời gian từ $O(min(x,y))$ xuống $O(log(max(x,y)))$. C++ có sẵn hàm gcd, tuy nhiên mình tự viết để các bạn khác có thể đọc qua.

int gcd(int x,int y){
    if (y==0) return x;
    else return gcd(y,x%y);
}
int t;cin>>t;
while (t--){
    int x,y,cnt=0;cin>>x>>y;
    while (gcd(x,y)==1) y++,cnt++;
    cout<<cnt<<"\n";
}

Độ phức tạp thời gian: $O(max(x,y).log(max(x,y)))$
### Subtask 3

**Nhận xét:** Nếu $x$ chia hết cho $d$ thì $gcd(x, k * d) \geq d$

Ước chung lớn nhất của $x$ và $y$ phải nằm trong tập ước của $x$, do đó ta sẽ duyệt qua các ước của $x$.

Gọi $d$ là ước của $x$.
Gọi $a$ là số nhỏ nhất sao cho $a$ chia hết cho $d$ và lớn hơn hoặc bằng $y$.
Ta có $a = d * k$
Ta sẽ cần tìm số nguyên $k$ nhỏ nhất sao cho $d * k \geq y$.
Ta có thể tìm $k$ bằng tìm kiếm nhị phân hoặc có công thức tính $k$ như sau:
$k$ = $\ \lfloor \frac{(y + d - 1)}{d} \rfloor$.(Với $\lfloor x \rfloor$ là làm tròn xuống của $x$)

Ta cần tìm min của $(k * d - y)$ với mỗi $d$ là ước của $x$ sao cho ước số đó lớn hơn 1.
Độ phức tạp thời gian: $O(sqrt(x))$.

**Giải thích thêm:** $k$ = $\ \lfloor \frac{y}{d} \rfloor$ trong trường hợp $y$ chia hết cho $d$, và $k$ = $\ \lfloor \frac{y}{d}\rfloor + 1$ trong trường hợp còn lại. Ta có công thức bao quát hơn như sau $k$ = $\ \lfloor \frac{(y + d - 1)}{d} \rfloor$.
#### Code mẫu C++

int calc(int x, int y) {

    int ans = 2 * x;

    for (int i = 1; i <= sqrt(x); i++) 
        if (x % i == 0) {

            if (i > 1) {

                int d = i;
                int num = ((y + d - 1) / d) * d;

                ans = min(ans, num - y);

            }

            if (x / i != i) {

                int d = x / i;
                int num = ((y + d - 1) / d) * d;

                ans = min(ans, num - y);

            }
       }

    return ans;

}