---
title
Contest 20/11 - Lời giải
---

Contest 20/11 - Lời giải
===

---

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

---

# Bài A. Siuuuuuu!!!

## Subtask 1
- Với subtask này, ta nhận thấy rằng giới hạn của $Q$ và $X$ đối với mỗi truy vấn là đủ nhỏ để tạo 1 mảng lưu các giá trị sau mỗi truy vấn và thực hiện thay đổi giá trị $Y_i$ đối với $X_i$ phần tử của truy vấn $i$.
- Độ phức tạp: $O\space(X*Q)$
## Subtask 2
- So với subtask 1, ta sẽ áp dụng 1 kĩ thuật đã từng được giới thiệu ở các bài viết trước của 2SG đó là sử dụng mảng hiệu sau đó thực hiện cộng dồn để có được 1 mảng lưu giá trị giống như subtask 1. Tuy nhiên, độ phức tạp đối với mỗi truy vấn $i$ lúc này giảm còn $O(1)$ thay vì $O(X_i)$. Cụ thể như sau
- Đối với truy vấn loại 1: thực hiện cộng vào phần tử đầu tiên giá trị $Y_i$ và trừ đi giá trị $Y_i$ ở phần tử $X_i + 1$
- Đối với truy vấn loại 2: thực hiện trừ đi giá trị $Y_i$ ở phần tử $N - X_i + 1$ và cộng vào giá trị $Y_i$ ở phần tử $N + 1$
- Độ phức tạp: $O\space(N + Q)$
## Subtask 3
- Với subtask này, cách tiếp cận sẽ có độ phức tạp khá giống subtask 2, tuy nhiên, do giới hạn của $N$ là quá lớn nên ta không thể tạo mảng đủ cho N phần tử được.
- Nếu đọc kĩ đề bài, ta thấy rằng đề yêu cầu tìm giá trị lớn nhất sau khi được thay bởi giá trị tuyệt đối, thế nên mình chỉ cần quan tâm đến 2 giá trị nhỏ nhất và lớn nhất của mảng $a$
- Với truy vấn loại $1$: Nó sẽ ảnh hưởng đến $X_i$ phần tử đầu tiên với $(1 \le X_i)$ nên nó sẽ luôn cộng giá trị $Y_i$ vào phần tử đầu tiên của mảng $a$ bất kể giá trị của $X_i$ $\Rightarrow$ phần tử đầu tiên **luôn** là phần tử lớn nhất
- Với truy vấn loại $2$: Tương tự như truy vấn loại $1$, ta cũng sẽ chỉ cần quan tâm đến phần tử cuối cùng của mảng do bất kể $X_i$ với $(1 \le X_i)$, phần tử cuối cùng luôn được trừ đi giá trị $Y_i$ $\Rightarrow$ phần tử cuối cùng **luôn** là phần tử nhỏ nhất
- Cuối cùng ta chỉ cần lấy max giá trị tuyệt đối của 2 phần tử này
- Độ phức tạp: $O\space(Q)$
- **Lưu ý:** Có 1 trường hợp đặc biệt và nó ảnh hưởng cả 2 truy vấn loại $1$ và $2$. Đó là nếu truy vấn ảnh hưởng $X_i = N$ phần tử thì cả giá trị lớn nhất và nhỏ nhất đều sẽ bị ảnh hưởng

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

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

#define ll long long

int main()
{
    ios_base::sync_with_stdio();
    cin.tie(0);
    int n, q;
    ll first, last;
    cin >> n >> q;
    first = last = 0;
    while (q--)
    {
        int query_type, x, y; cin >> query_type >> x >> y;
        if (query_type == 1)
        {
            first += y;
            if (x == n) last += y;
        }
        else
        {
            last -= y;
            if (x == n) first -= y;
        }
    }
    cout << max(abs(first), abs(last));
    return 0;
}

:::

# Bài B. Hit The Stage
- Có thể thấy với mỗi cặp $(i, j)$ sao cho $i < j$, số lượng số nguyên dương $k$ thỏa mãn $i \le k \le j$ là $j-i+1$, như vậy độ ăn ý của một cặp bạn ($i, j$) là $a_i \cdot a_j\cdot(j-i+1)$.
## Subtask 1
- Ở subtask này có $n \le 1000$, vì thế ta sẽ sử dụng hai vòng lặp `for` lồng nhau để duyệt qua mọi cặp bạn ($i, j$) khác nhau, từ đó tính độ hợp ý của mỗi cặp và tính tổng, lưu ý sử dụng `long long` để tránh tràn số và chia lấy dư cho $10^9+7$.
:::spoiler **Code mẫu**

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

int main()
{    
    int n;
    long long ans = 0;
    cin >> n;

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

    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            ans = (ans+(long long)a[i]*a[j]%mod*(j-i+1))%mod;

    cout << ans;
    return 0;
}

:::
## Subtask 2
- Ở subtask này, mọi phần tử trong mảng $a$ đều có cùng một giá trị nào đó, gọi giá trị này là $x$.
- Như vậy, độ hợp ý của một cặp bạn ($i, j$) sẽ là $x^2\cdot(j-i+1)$, sử dụng nhân phân phối, biểu thức trên sẽ thành $x^2\cdot j-x^2 \cdot i+x^2$.
- Ta duyệt chỉ số $j$ lần lượt từ $1$ đến $n$, với mỗi chỉ số $j$, ta tính tổng độ hợp ý của toàn bộ cặp $(i, j)$ với $i < j$, ta có biểu thức của tổng ấy như sau:

$$x^2\cdot j-x^2 \cdot i+x^2 + x^2\cdot j-x^2 \cdot (i-1)+x^2+ x^2\cdot j-x^2 \cdot (i-2)+x^2+...+ x^2\cdot j-x^2 \cdot 1+x^2$$

- Thu gọn biểu thức trên, ta được biểu thức sau:
$$(j-1)\cdot x^2\cdot j - x^2\cdot(1+2+...+(j-2)+(j-1))+x^2\cdot(j-1)$$

- Như vậy với mỗi $j$, ta có thể tính được tổng độ hợp ý của toàn bộ cặp $(i, j)$ với biểu thức trên chỉ với một vòng lặp.
:::spoiler **Code mẫu**

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

int main()
{    
    int n;
    long long ans = 0;
    cin >> n;

    int a[n + 1], sum = 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long x = (long long)a[1]*a[1]%mod;
    for (int j = 1; j <= n; j++)
    {
        ans = (ans+(j-1)*x%mod*j-x*sum%mod+x*(j-1)%mod+mod)%mod;
        sum = (sum+j)%mod;
    }

    cout << ans;
    return 0;
}

:::

## Subtask 3

Giống với subtask trên, thế nhưng điểm khác biệt ở subtask này là $a_i \ne a_j$, chúng ta sẽ vẫn nhân phân phối biểu thức $a_i \cdot a_j \cdot (j - i + 1)$ và ta được biểu thức $a_j \cdot [(j + 1) \cdot a_i - i \cdot a_i]$, từ đây ta có biểu thức tính tổng độ hợp ý như sau:
$$
a_j \cdot [(j + 1) \cdot a_1 - 1 \cdot a_1] + a_j \cdot [(j + 1) \cdot a_2 - 2 \cdot a_2] + ... + a_j \cdot [(j + 1) \cdot a_i - i \cdot a_i] \space (i = j - 1)
$$

Rút nhân tử chung, ta được:
$$
a_j \cdot [(j+1) \cdot (a_1 + a_2 + ... + a_i) - (1 \cdot a_1 + 2 \cdot a_2 + ... + i \cdot a_i)] \space (i = j - 1)
$$

Gọi $pref1_i = a_1 + a_2 + ... + a_i, pref2_i = 1 \cdot a_1 + 2 \cdot a_2 + ... + i \cdot a_i$. Thế vào biểu thức trên ta được:
$$
a_j \cdot [(j + 1) \cdot pref1_{j-1} + pref2_{j-1}]
$$
Từ đó với mỗi $j$, ta có thể tính được tổng toàn bộ các cặp $(i, j)$ trong 1 vòng lặp. 2 mảng $pref1, pref2$ có thể được xây dựng trước bên ngoài.

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

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

const int maxn = 1e5 + 5;
const int MOD = (int)1e9 + 7;
ll a[maxn], pref1[maxn], pref2[maxn];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref1[i] = (pref1[i-1] + a[i])%MOD;
        pref2[i] = (pref2[i-1] + a[i]*i)%MOD;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll sum = ((i + 1)*pref1[i-1] % MOD - pref2[i-1] + MOD) % MOD;
        ans += ((a[i] % MOD) * (sum % MOD))%MOD;
        ans %= MOD;
    }
    cout << ans;
}

:::

# Bài C. Flowers

## Subtask 1
- Với subtask này, vì sau khi thực hiện phép nối mọi phần tử trong dãy lại với nhau thì kết quả chỉ có tối đa 16 chữ số ($n \le 8$, $a_i \le 99$) và vì mỗi phần tử chỉ có 1 chữ số nên ta chỉ cần sắp xếp lại dãy theo thứ tự giảm dần rồi nối các phần tử trong dãy lại với nhau. Lưu ý là ta phải dùng kiểu dữ liệu ```long long``` vì đáp án có thể lên tới $9999999999999999$
- Ta sắp xếp theo thứ tự giảm dần vì điều này đảm bảo các chữ số lớn hơn sẽ có thể đứng ở vị trí gần với tận cùng bên phải hơn nên kết quả sẽ là lớn nhất có thể.
+ VD: với dãy ```19 71 25``` thì ta sắp xếp lại theo thứ tự giảm dần là ```71 25 19``` để có kết quả lớn nhất có thể là ```712519```, mọi cách sắp xếp còn lại đều không thể tạo ra kết quả lớn bằng.

## Subtask 2
- Từ subtask này, ta bắt đầu phải lưu mọi phần tử $a_i$ của dãy dưới dạng ```string``` để xử lí bài toán vì mỗi phần tử có thể lên đến 69 chữ số ($a_i \le 10^{69}$) nên không thể lưu bằng ```int``` hay ```long long``` .
- Ta vẫn sắp xếp lại dãy số nhưng vì $n$ nhỏ ($n \le 2 * 10^2$) nên ta có thể sử dụng thuật toán sắp xếp bubble sort với một chút biến tấu:
+ Ta không thể sử dụng phép toán so sánh $a_i < a_j$ ($1 \le i, j \le n$ và $i \neq j$) như khi thực hiện bubble sort bình thường (vì mọi phần tử $a_i$ là string chứ không phải số) mà ta phải xây dựng một hàm để so sánh các cặp string $a_i$ và $a_j$ theo cách như sau.
+ Chú thích: $|x|$ là độ dài của string $x$.
+ **So sánh $x + y$ và $y + x$**
+ Với cách làm này, để so sánh việc nên đặt $x$ hay $y$ ở phía trước trong dãy số để có được kết quả tối ưu thì ta tạo thêm 2 string là $S = x + y$ và $T = y + x$ sau đó so sánh 2 string này theo thứ tự từ điển như trên mà không cần phải lo lắng đến trường hợp $|x| \neq |y|$.
+ Sau khi so sánh $a_i$ và $a_j$ (theo thứ tự từ điển) xong thì ta vẫn hoán đổi vị trí của chúng dựa trên kết quả của phép so sánh như khi thực hiện bubble sort bình thường.
- Sau khi sắp xếp dãy số theo thứ tự giảm dần (theo thứ tự từ điển) xong thì ta duyệt qua các phần tử của dãy số và nối chúng lại với nhau. Kết quả bài toán là số (dưới dạng ```string```) mà ta thu được sau khi nối mọi phần tử của dãy số.

## Subtask 3
- Ta thực hiện subtask này y như cách thực hiện subtask 2, nhưng là với quick sort thay vì bubble sort vì $n$ lớn ($n \le 2 * 10^4$)
- Ngoài việc tự code ra thuật toán quick sort với hàm so sánh 2 string theo thứ tự từ điển đã nêu trên, thì ta cũng có thể sử dụng hàm ```sort``` có sẵn của C++ theo cú pháp ```sort(arr + 1, arr + 1 + n, cmp)``` với ```arr``` là mảng chứa dãy số và ```cmp``` là hàm kiểu```bool``` để so sánh 2 string $x$ và $y$ theo thứ tự từ điển.

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

#include <bits/stdc++.h>

using namespace std;

string a[20005];

bool cmp(string x, string y)
{
    string S = x + y;
    string T = y + x;
    if (T > S) return(false);
    else return(true);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // sort(a + 1, a + n + 1, [](string x, string y) {return x + y > y + x;});
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) cout << a[i];

    return 0;
}

:::

# Bài D. Drop The Mic

## Subtask 1 (50%)
- Ở subtask 1 này đơn giản là đề nói gì làm đó, chúng ta sẽ duyệt 2 vòng lặp lồng nhau và lưu lại vào mảng $c$ tất cả các $a_i \times b_j$. Sau đó sort mảng $c$ lại và in ra $c_k$. Độ phức tạp $O(n^2\log{n})$.

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

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

const int maxn = 1e5 + 5;
long long a[maxn], b[maxn];

void solve() {
    int k, n, m; cin >> k;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> b[i];
    vector<long long> ans;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) ans.push_back(a[i]*b[j]);
    }
    sort(ans.begin(), ans.end());
    cout << ans[k-1] << endl;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //   freopen("test.inp", "r", stdin);
    //   freopen("test.out", "w", stdout);
    int t = 1;
    while (t--) solve();
    return 0;
}

/**
  *    {\__/}
  *    (• .•)
  *    / >♥️
**/

:::

## Subtask 2 (50%)
- Ở subtask 2 này chúng ta sẽ thử lật ngược bài toán lại như sau: Giả sử $x$ là kết quả mà chúng ta đang cần tìm, $p$ là số lượng số $a_i \times b_j \le x$, vậy $x$ chỉ thoả mãn khi $p = k$. Từ đây chúng ta có thể dùng tìm kiếm nhị phân để tìm một giá trị $x$ nhỏ nhất thoả mãn.
- Thế nhưng nếu chúng ta tìm $p$ trong $O(n^2)$ thì thuật toán của ta lúc này sẽ không khác gì subtask 1 ($O(n^2\log{n})$). Vậy nên chúng ta cần một thuật toán khác để tìm nhanh chóng $p$ trong $O(n)$.
### Trường hợp 1: a toàn dương và b toàn dương
- Trong trường hợp này, ta sẽ sort toàn bộ mảng $a$ và $b$ tăng dần. Nếu cố định $a_i$, ta sẽ tìm $j$ xa nhất sao cho $a_i \times b_j \le x$, hay tìm $j$ xa nhất sao cho $b_j \le \lfloor \frac{x}{a_i} \rfloor$ bằng cách sử dụng tìm kiếm nhị phân hoặc hai con trỏ. Khi đó $a_i \times b_1, a_i \times b_2, ..., a_i \times b_j$ đều bé hơn hoặc bằng $x$. Vậy kết quả sẽ là $j_1 + j_2 + ... + j_n$ trong đó $j_i$ là vị trí xa nhất sao cho $a_i \times b_{j_i} \le x$.

### Trường hợp 2: a toàn dương và b toàn âm
- Tương tự trường hợp 1, ta sẽ sort toàn bộ mảng $a$ và $b$ tăng dần. Nếu cố định $a_i$, ta sẽ tìm $j$ xa nhất sao cho $a_i \times b_j \le x$, hay tìm $j$ xa nhất sao cho $b_j \le \lfloor \frac{x}{a_i} \rfloor$ bằng cách sử dụng tìm kiếm nhị phân hoặc hai con trỏ. Khi đó $a_i \times b_1, a_i \times b_2, ..., a_i \times b_j$ đều bé hơn hoặc bằng $x$. Vậy kết quả sẽ là $j_1 + j_2 + ... + j_n$ trong đó $j_i$ là vị trí xa nhất sao cho $a_i \times b_{j_i} \le x$.

### Trường hợp 3: a toàn âm và b toàn dương
- Tương tự trường hợp 1 và 2, ta sẽ sort toàn bộ mảng $a$ và $b$ tăng dần. Nếu cố định $b_i$, ta sẽ tìm $j$ xa nhất sao cho $a_j \times b_i \le x$, hay tìm $j$ xa nhất sao cho $a_j \le \lfloor \frac{x}{b_i} \rfloor$ bằng cách sử dụng tìm kiếm nhị phân hoặc hai con trỏ. Khi đó $a_1 \times b_i, a_2 \times b_i, ..., a_j \times b_i$ đều bé hơn hoặc bằng $x$. Vậy kết quả sẽ là $j_1 + j_2 + ... + j_n$ trong đó $j_i$ là vị trí xa nhất sao cho $a_{j_i} \times b_i \le x$.

### Trường hợp 4: a toàn âm và b toàn âm
- Trong trường hợp này, ta sẽ sort toàn bộ mảng $a$ và $b$ tăng dần. Nếu cố định $a_i$, ta sẽ tìm $j$ gần nhất sao cho $a_i \times b_j \le x$, hay tìm $j$ gần nhất sao cho $b_j \le \lfloor \frac{x}{a_i} \rfloor$ bằng cách sử dụng tìm kiếm nhị phân hoặc hai con trỏ. Khi đó $a_i \times b_j, a_i \times b_{j+1}, ..., a_i \times b_m$ đều bé hơn hoặc bằng $x$. Vậy kết quả sẽ là $m - j_1 + 1 + m - j_2 + 1 + ... + m - j_n + 1$ trong đó $j_i$ là vị trí gần nhất sao cho $a_i \times b_{j_i} \le x$.

Tóm lại ta chỉ cần tách ra $4$ mảng $a1, b1, a2, b2$ để lưu lần lượt các giá trị dương của mảng $a$, $b$ và các giá trị âm của mảng $a$, $b$ và làm ra $4$ trường hợp đã nêu trên.

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

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

long long n, m, k;
vector<long long> a1, b1, a2, b2;

bool check(long long x) {
    long long ans = 0;
    int j = b1.size() - 1;
    for (int i = 0; i < a1.size(); i++) {
        while (j >= 0 && a1[i]*b1[j] > x)
            j--;
        ans += j + 1;
    }
    j = b2.size() - 1;
    for (int i = a1.size() - 1; i >= 0; i--) {
        while (j >= 0 && a1[i]*b2[j] > x)
            j--;
        ans += j + 1;
    }
    j = a2.size() - 1;
    for (int i = b1.size() - 1; i >= 0; i--) {
        while (j >= 0 && b1[i]*a2[j] > x)
            j--;
        ans += j + 1;
    }
    j = 0;
    for (int i = a2.size() - 1; i >= 0; i--) {
        while (j < b2.size() && a2[i]*b2[j] > x)
            j++;
        ans += b2.size() - j;
    }
    return ans >= k;
}

void solve() {
    cin >> k;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        if (x >= 0) a1.push_back(x);
        else a2.push_back(x);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        long long x; cin >> x;
        if (x >= 0) b1.push_back(x);
        else b2.push_back(x);
    }
    sort(a1.begin(), a1.end());
    sort(b1.begin(), b1.end());
    sort(a2.begin(), a2.end());
    sort(b2.begin(), b2.end());
    long long l = -1e18, r = 1e18, ans = -1;
    while (l <= r) {
        long long x = l + (r - l) / 2;
        if (check(x)) {
            r = x - 1;
            ans = x;
        } else l = x + 1;
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //   freopen("test.inp", "r", stdin);
    //   freopen("test.out", "w", stdout);
    int t = 1;
    while (t--) solve();
    return 0;
}

/**
  *    {\__/}
  *    (• .•)
  *    / >♥️
**/

:::

# Bài E. Riddles

## Tóm tắt đề
- Cho 2 số nguyên $n$ và $k$. Tính $S = \overline{k} + \overline{kk} + \overline{kkk} + ... + \overline{kkk...kk}$.

## Subtask 1

- Ở subtask 1 ta có $n \le 6$ nên tất các số ta cần lấy sẽ nằm trong khoảng $[1..10^7$]. Ta duyệt hết tất cả số trong khoảng này và cộng $n$ số đầu tiên thỏa đề bài chỉ chứa chữ số $k$.

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

#include <bits/stdc++.h>

using namespace std;

bool check(int x, int k)
{
    while(x)
    {
        if(x % 10 != k) return false;
        x /= 10;
    }
    return true;
}

int main()
{
    int n, k, ans = 0, gifted = 0;
    cin >> n >> k;
    for(int i = 1; i <= 10000000; ++i)
    {
        if(check(i, k))
        {
            ++gifted;
            ans += i;
        }
        if(gifted == n) break;
    }
    cout << ans << endl;
    return 0;
}

:::

## Subtask 2

- Vì $n \le 10^5$, có thể có đến tối đa $10^5$ chữ số trong 1 con số. Ta không thể duyệt hết từng số để kiểm tra được.
- Xét số có dạng $\overline{kkk...kk}$ có $n$ chữ số $k$. Liệu ta có thể tính được con số này dựa vào con số trước có dạng tương tự với $n-1$ chữ số hay không ?
::: success
::: spoiler Đáp án
- Đáp án là có.
- $\overline{kkk...kk}$ ($n$ chữ số) = $\overline{kkk...k}$ ($n-1$ chữ số) $\cdot 10 + k$
:::
- Dựa vào câu trả lời cho câu hỏi trên, ta sẽ có được câu trả lời cho subtask này bằng 1 vòng for.
- Tuy nhiên, vì số lớn nhưng chỉ yêu cầu in ra theo modulo, ta cần áp dụng những kiến thức về cộng, trừ, nhân trong [Đồng dư thức](https://hackmd.io/EomwVdxnT663LQaC80_Zig#%C4%90%E1%BB%93ng-d%C6%B0-th%E1%BB%A9c).

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

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;

int main()
{
    int n, k;
    long long ans = 0, prev = 0;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
    {
        ans += prev * 10 + k;
        ans %= mod;
        prev = prev * 10 + k;
        prev %= mod;
    }
    cout << ans << endl;
    return 0;
}

:::

## Subtask 3

- Với $n \le 2\cdot10^9$, ta không còn có thể duyệt trong độ phức tạp tuyến tính, ta thậm chí cần tìm một thuật toán tối ưu hơn.
- Thực hiện biến đổi chút với dãy $S$ như sau:
::: info
$S = \overline{k} + \overline{kk} + \overline{kkk} + ... + \overline{kkk...kk}$
$= \frac{k}{9} \cdot (9 + 99 + 999 + + ... + \overline{999...99})$
$= \frac{k}{9} \cdot (10 + 100 + ... + 10^n - n)$
$= \frac{k}{9} \cdot (10 \cdot (\overline{111...11})$ ($n$ chữ số) $- n)$
$= \frac{k}{9} \cdot (\frac{10}{9} \cdot (\overline{999...99})$ ($n$ chữ số) $- n)$
$= \frac{k}{9} \cdot (\frac{10 \cdot (10^n - 1)}{9} - n)$
:::

- Với $k = 9$ thì việc xử lí phân số ở ngoài đã được giảm đi, ta chỉ cần tìm $\frac{10 \cdot (10^n - 1)}{9} - n$
- Vậy là ta đã tìm được công thức tổng quát của $S$. Tuy nhiên, ta còn cần phải xử lí phép lũy thừa và modulo, trong đó có cả phép chia.
- Ta có thể tính lũy thừa nhanh trong độ phức tạp $O(\log n)$ bằng thuật toán **Binary Exponentiation** và xử lí chia modulo với nghịch đảo modulo. Phần kiến thức này tương đối nâng cao, có thể sẽ được trình bày rõ hơn trong các bài viết sắp tới.

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

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const long long inverse = 111111112; // Nghịch đảo modulo của 9, ta có thể tính = công thức 9^(mod-2)%mod do `mod` là số nguyên tố

long long binpow(long long a, long long b)
{
    if(b == 0) return 1;
    long long temp = binpow(a, b / 2);
    if(b % 2) return (((temp * temp) % mod) * a) % mod;
    else return (temp * temp) % mod;
}

int main()
{
    // CODE NÀY CHỈ AC ĐƯỢC TRONG TRƯỜNG HỢP N > 10000000
    int n, k;
    cin >> n >> k;
    cout << (((10 * (binpow(10, n) - 1 + mod) % mod) * inverse % mod) - (n % mod) + mod) % mod << endl;
    return 0;
}

:::

# Bài F. Love Sweet Love

## Subtask 1
Các bạn chỉ cần for trâu từng cặp $(i, j)$ thỏa mãn
## Subtask 2
Gọi $f_i=\gcd(1, i)+\gcd(2, i)+\gcd(3, i)+...+\gcd(i-1, i)$
Với mỗi truy vấn, ta cần tính $\sum_{i=1}^n f_i$.
Nhận thấy biểu thức $\sum_{i=1}^n f_i$ có thể được xử lý bằng mảng cộng dồn nên ta sẽ **tiền xử lý** bằng cách tính các $f_i$ trước.
## Subtask 3
Trước khi đi vào subtask 3, mình xin sử dụng một số khái niệm sau :
- $D(x)$ : biểu diễn tập hợp các ước của $x$, VD : $D(10)=\{1, 2, 5, 10\}$
- $\varphi(x)$ : [Phi hàm Euler](https://vi.wikipedia.org/wiki/H%C3%A0m_phi_Eulerc) của số nguyên dương $x$, hay nói các khác $\varphi(x)$ là số lượng số $y$ thỏa $1\leq y\leq x$ và $\gcd(x, y)=1$, VD : $\varphi(10)=4$ vì chỉ có $1, 3, 7, 9$ thỏa.

Cũng như subtask 2, ta định nghĩa lại :
- $f_i=\gcd(1, i)+\gcd(2, i)+\gcd(3, i)+...+\gcd(i-1, i)$
- $f_i =\sum_{j=1}^{i-1} \gcd(j ,i)$

Ta thấy rằng với mọi $\gcd(j, i)$, nó sẽ là một **ước số** của $i$. Chính vì điều này, ta thay đổi lại cách ta tính $f_i$ nhanh hơn cách ở subtask 2

- gọi $D(x)$ là tập hợp các ước của $x$
- $f_i = \sum_{d \in D(i)} d \times$(số cặp $\gcd(j, i)=d$)

Ta lại có một tính chất số học quan trọng khác : $\gcd(x, y)=d \Leftrightarrow \gcd(\frac{x}{d}, \frac{y}{d})=1$.
Từ tính chất này suy ra :

- $f_i = \sum_{d \in D(i)} d \times$(số cặp $\gcd(\frac{j}{d}, \frac{i}{d})=1$)
- Bất ngờ thay (số cặp $\gcd(\frac{j}{d}, \frac{i}{d})=1$) chính là $\varphi(\frac{i}{d})$

Cuối cùng ta có công thức $f_i=\sum_{d \in D(i)} d \times \varphi(\frac{i}{d})$

Bằng cách sử dụng **Sàng nguyên tố**, chúng ta có thể tính $\varphi(i)$ và $f_i$ nhanh hơn. Độ phức tạp : $O(10^6 \log(10^6))$

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

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

typedef long long ll;

int phi[N]; //phi(x)
ll f[N], sum[N]; //f[x] = gcd(1, x) + gcd(2, x) + gcd(3, x) + ... + gcd(x-1, x)

void phiSieve(){
    for(int i =1 ; i <= 1000000; ++i){
        phi[i] = i;
    }

    for(int i = 2; i <= 1000000; ++i){
        if(phi[i] == i){
            ///i is prime
            for(int j = i; j <= 1000000; j += i){
                    phi[j] -= phi[j] / i;
            }
        }
    }
}

void solveF(){
    for(int i = 1; i <= 1000000; ++i){
        for(int j = 2 * i; j <= 1000000; j += i){
            f[j] += 1ll * i * phi[j/i];
        }
    }

    for(int i = 1; i <= 1000000; ++i){
        sum[i] = sum[i-1] + f[i];
    }
}

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

    phiSieve();
    solveF();

    int q; cin >> q;
    while(q--){
        int n; cin >> n;
        cout << sum[n] << '\n';
    }

    return 0;
}

:::