# Bài 1: Số đặc biệt

## :memo: Tóm tắt đề bài
*Đếm trong đoạn $[L, R]$ có bao nhiêu số có thể biểu diễn dưới dạng $n^2 + 2n - 1$, $n \in N$.*

Các subtask lần lượt là:
Sub 1: 1 $\leq L \leq R \leq 100$
Sub 2: 1 $\leq L \leq R \leq 10^4$
Sub 3: 1 $\leq L \leq R \leq 10^{12}$

**Dữ liệu (Input/Output):**

- Input: hai số nguyên L, R

- Output: In ra đáp án của bài toán

---

## :bulb: Ý tưởng & Giải thuật

### 1. Phân tích ban đầu

*Với Sub 1 và Sub 2, ta hoàn toàn có thể duyệt trâu và in ra kết quả mà vẫn đảm bảo về mặt thời gian. Với Sub 3, ta chỉ cần thay đổi cách duyệt một chút.*

---

### 2. Chiến lược giải quyết

#### 2.1. Duyệt trâu

*Ta hoàn toàn có thể duyệt qua từng số $i$ trong đoạn $[L, R]$, với mỗi số $i$ thì duyệt các số $k$ từ 1 tới $i - 1$ xem xem số i này có thể biểu diễn dưới dạng $n^2 + 2n - 1$ hay không*

#### :computer: Code mẫu

int cnt = 0;

// để i là int do giải pháp duyệt trâu chỉ thức hiện được với sub 1 và sub 2
for (int i = l; i <= r; ++i){
    
    for (int k = 1; k < i; ++k){
        int curr = k*k + 2*k - 1;
        
        if (curr == i){
            ++cnt;
            break;
        }
    }
}

cout << cnt;

---

#### 2.2. Đánh giá độ phức tạp

:::info
Với mỗi số $i$ trong đoạn $[L, R]$, ta duyệt từ 1 đến $i - 1$
Tức ta duyệt lần lượt:
$(l - 1) + l + (l + 1) + ... + (r - 1)$ số
Hay $\frac{r(r - 1) - (l - 1)(l - 2)}{2}$ số

ĐPT: O($\frac{r(r - 1) - (l - 1)(l - 2)}{2}$)
Tối đa 4.950 thao tác với Sub 1 và 49.995.000 thao tác với Sub 2, hoàn toàn có thể AC được.
:::

---

#### 2.3. Tối ưu

*Dễ thấy rằng nếu một số $i$ có thể biểu diễn dưới dạng $n^2 + 2n - 1$ thì $n^2 < i$. Vậy ta chỉ cần các số $k$ trong khoảng $[1, \sqrt{R}]$ và kiểm tra xem:*
*$k^2 + 2k -1 \geq L$*
*$k^2 + 2k -1 \leq R$*

***Note: sau khi người ra đề test lại thì duyệt từ $\sqrt{L}$ đến $\sqrt{R}$ vẫn AC nhưng thực hiện theo cách này để đảm bảo :)***

## :computer: Code mẫu

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll l, r, cnt = 0;

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    freopen("sodacbiet.inp", "r", stdin);
    freopen("sodacbiet.out", "w", stdout);
    
    cin >> l >> r;
    
    ll  en = sqrt(r);
    
    for (ll i = 1; i <= en; ++i){
        ll curr = i*i + 2*i - 1;
        
        if (curr >= l && curr <= r) 
            ++cnt;
    }
    
    cout << cnt;
}

---

#### 2.4. Đánh giá độ phức tạp

:::info
ĐPT O($\sqrt{R}$)
:::

---

# Bài 2 - Sức mạnh của xâu (STRSTRENGTH)
## Ý tưởng
* Sức mạnh của một chuỗi ký tự được định nghĩa là giá trị trung bình cộng các mã ASCII của tất cả các ký tự trong chuỗi.
* Với chuỗi có độ dài $n$, ký tự thứ $i$ có mã ascii là $a_i$ thì sức mạnh của xâu đó sẽ là $(a_1+a_2+...+a_n)/n$
## Thuật toán
- Đọc toàn bộ chuỗi ký tự S.
- Duyệt qua từng ký tự trong chuỗi:
- Chuyển ký tự sang mã ASCII
- Cộng vào tổng
- Tính trung bình
- Lấy tổng chia cho độ dài chuỗi
- In ra kết quả với 3 chữ số sau dấu phẩy
#### Độ phức tạp của thuật toán: $O(|S|)$
## Code mẫu:

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

int main() {
    freopen("STRSTRENGTH.INP", "r", stdin);
    freopen("STRSTRENGTH.OUT", "w", stdout);

    string S;
    getline(cin, S);

    double sum = 0;
    for (char c : S) {
        sum += c;
    }

    double strength = sum / S.length();

    cout << fixed << setprecision(3) << strength;
 
}

# Bài 3 - Finger Math (FM)
::::info
:::spoiler 💡 Hint 1
Để 1 số được nằm ở giữa thì vị trí nó phải như nào?
:::
::::

::::info
:::spoiler 💡 Hint 2
Để 1 số nằm ở giữa thì số đó phải là số đầu tiên > $\lfloor \frac{n*n}{2} \rfloor$ số
:::
::::

::::info
:::spoiler 💡 Hint 3
Từ nhận định trên thì ta có thể tối ưu solution thành $\mathcal{O}(nlogn)$ không?
:::
::::

## Subtask 1
:::: spoiler Solution ✅
Ở subtask này, ta có 2 hướng:
1. Sinh test tay ra từ 1 -> 10 (5 trường hợp do $n$ luôn lẻ), xong xét điều kiện if else
2. Thực hiện hướng tiếp cận ở subtask 2
:::info
Độ phức tạp thuật toán: $\mathcal{O}(1)$
:::
::::

::: spoiler Code 💻

#include <iostream>
#include <vector>

using namespace std;

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void setup(){
    if(!fopen("FM.INP", "r")) return;
    freopen("FM.INP", "r", stdin);
    freopen("FM.OUT", "w", stdout);
}

int main(){
    fast();
    setup();
    
    int n;
    cin >> n;
    if(n == 1){
        cout << 1;
    }
    else if(n == 3){
        cout << 3;
    }
    else if(n == 5){
        cout << 8;
    }
    else if(n == 7){
        cout << 12;
    }
    else{
        cout << 20;
    }
}

:::

## Subtask 2
:::: spoiler Solution ✅
Với $n$ nhỏ ($n <= 10^3$) thì ta hoàn toàn có thể sinh ra mọi trường hợp, do đó chiến thuật của ta là tạo 2 vòng for sau đó thêm các giá trị được tạo bởi $i*j$ vào 1 mảng 1D, sau đó ta sort lại và lấy vị trí $\lceil \frac{n*n}{2} \rceil$
:::info
Độ phức tạp thuật toán: $\mathcal{O}(n^2 * log(n^2))$
:::
::::

::: spoiler Code 💻

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void setup(){
    if(!fopen("FM.INP", "r")) return;
    freopen("FM.INP", "r", stdin);
    freopen("FM.OUT", "w", stdout);
}

int main(){
    fast();
    setup();
    
    int n;
    cin >> n;
    vector<long long> a(n*n);
    int cur_idx = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[cur_idx++] = i*j;
        }
    }
    sort(a.begin(),a.end());
    cout << a[n*n/2];
}

:::

## Subtask 4
:::: spoiler Solution ✅
Để chạy code trong $\mathcal{O}(nlogn)$, ta có thể chặt nhị phân đáp án. Cụ thể như sau:
1. Gọi $x$ là số cần tìm. Ta cần đếm số lượng số <= $x$
2. Đáp án của đề bài đó là số $x$ nhỏ nhất sao cho $x >= \lfloor \frac{n*n}{2} \rfloor$
3. Để đếm số lượng số < $x$ mà nằm trong ma trận, ta có thể for qua từng $i$ từ 1 tới $n$, sau đó đếm tổng số lượng $frac{x}{i}$ (số lượng đại diện cho các số < $x$ được tạo bởi $i$ nhân với 1 số nào đó)
:::info
Độ phức tạp thuật toán: $\mathcal{O}(nlogn)$
:::
::::

::: spoiler Code 💻

#include <iostream>
#include <vector>

using namespace std;

long long n, target;

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void setup(){
    if(!fopen("FM.INP", "r")) return;
    freopen("FM.INP", "r", stdin);
    freopen("FM.OUT", "w", stdout);
}

bool check(long long mid){
    long long cnt = 0;
    for(int i = 1; i <= n; i++){
        cnt += min(n,mid/i);
    }
    return cnt >= target;
}

int main(){
    fast();
    setup();
    
    cin >> n;
    target = (n*n+1)/2;

    long long l = 1, r = n*n, ans = -1;
    while(l <= r){
        long long mid = l + ((r-l)>>1);
        if(check(mid)){
            ans = mid;
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
    cout << ans;
}

:::

# Bài 4: GAME

## :memo: Tóm tắt đề bài
*Đầu vào cho bạn 2 số $n$ và $q$. $(n, q\leq10^4)$*
*Ban đầu bạn có mảng A với $n$ phần tử $(A_i \leq 10^6)$, $q$ truy vấn tiếp theo sẽ xảy ra một trong hai loại:*

*- 1 L R x: thay đổi tất cả giá trị trong khoảng $[L, R]$ thành x*
*- 2 L R: Tính tích các $\phi(x)$* với x là những giá trị thuộc đoạn $[L, R]$, $\phi(x)$ là phi hàm Euler của $x$, mod cho $10^9 + 7$

**Dữ liệu (Input/Output):**

- Input:
- Dòng đầu chứa hai số $n, q$
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2,..,a_n$
- $q$ dòng tiếp theo là các truy vấn loại 1 hoặc 2

- Output: In ra đáp án của các truy vấn loại 2 trên từng dòng.

---

## :bulb: Ý tưởng & Giải thuật

### 1. Trâu

Ta đơn giản sẽ xử lý các truy vấn như sau:
- Truy vấn loại 1: duyệt qua tất cả các số trong đoạn L, R và thay chúng bằng x
- Truy vấn loại 2: tính tích phi hàm Euler các giá trị trong đoạn $[L, R]$

Đối với công đoạn tính phi hàm Euler cho mỗi giá trị, ta có thể làm một hàm riêng, kết hợp với sàng nguyên tố.

Do với mỗi giá trị x, $\phi(x)$ = $\prod_{i=1}^{k}(p_i^{q_i} - p_i^{q_i - 1})$

Biến đổi một chút ta có: $\phi(x)$ = $\prod_{i=1}^{k}(p_i^{q_i}(1 - \frac{1}{p_i}))$

Vậy ta sẽ có: Biến đổi một chút ta có: $\phi(x)$ = $\prod_{i=1}^{k}p_i^{q_i} * \prod_{i=1}^{k}(1 - \frac{1}{p_i})$

Vậy cuối cùng, ta có $\phi(x) = x.\prod_{i=1}^{k}(1 - \frac{1}{p_i})$

#### :computer: Code minh hoạ

#include <bits/stdc++.h>
using namespace std;
int a[1005], n, q;
bool p[1005];
vector<int> prime;

void sang(){
    // duyệt tới 1000 do cách này chỉ đảm bảo AC trong hai sub đầu

    p[0] = p[1] = 1;
    for (int i = 2; i * i <= 1000; ++i){
        if(!p[i]){
            for (int j = i * i; j <= 1000; j += i){
                p[j] = 1;
            }
        }
    }

    for (int i = 2; i <= 1000; ++i){
        if (!p[i]) prime.push_back(i);
    }
}

ll phi(ll x){
    if (x == 1) return 1;
    
    ll res = x;
    
    for (int ps : prime){
        if (x % ps == 0){
            res -= res / ps;
        }
    }
    
    return res;
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    freopen("GAME.INP", "r", stdin);
    freopen("GAME.OUT", "w", stdout);
    
    cin >> n >> q;
    
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    sang();
    while(q--){
        int type;
        cin >> type;
        
        if (type == 1){
            int l, r, x; 
            cin >> l >> r >> x;
            
            for (; l <= r; ++l) a[l] = x;
        }
        else{
            int l, r;
            cin >> l >> r;
            
            long long res = 1;
            
            for (; l <= r; ++l) res *= phi(a[l]);
        }
    }
}

ĐPT tối đa O($n.q.m$). Với $m$ là số lượng thao tác tính $\phi(x)$

### 2. Cải tiến

Ta sẽ tính sẵn phi của các giá trị $x$, do $x$ tối đa chỉ lên tới $10^6$, hoàn toàn có thể sử dụng sàng để tính

#### :computer: Code minh hoạ

const int maxn = 1e6 + 5;
int phi[maxn];

// Sàng phi(x)
for (int i = 1; i < maxn; ++i) phi[i] = i;

for (int i = 2; i * i < maxn; ++i){
    if (phi[i] == i){
        for (int j = i * i; j < maxn; j += i){
            phi[j] -= phi[j] / i;
        }
    }
}

Khi này ĐPT của việc tính $\phi(x)$ là O(1).

ĐPT tổng thể còn O($n.q$).

### 3. Solution

Để xử lý truy vấn loại 2 một cách tối ưu và cập nhật truy vấn loại 1, ta sẽ sử dụng Segment Tree + Lazy Propagation.

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

const int max_val = 1000005, maxn = 1e4 + 5, MOD = 1e9 + 7;

int phi[max_val], n, q, a[maxn], lazy[4 * maxn];

long long tree[4 * maxn];

void sang_phi() {
    for (int i = 0; i < max_val; i++) phi[i] = i;
    for (int i = 2; i < max_val; i++) {
        if (phi[i] == i) {
            for (int j = i; j < max_val; j += i)
                phi[j] -= phi[j] / i;
        }
    }
}

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

void push(int id, int l, int r) {
    if (lazy[id] != 0) {
        int mid = (l + r) / 2;
        
        lazy[2 * id] = lazy[id];
        tree[2 * id] = power(lazy[id], mid - l + 1);
        
        lazy[2 * id + 1] = lazy[id];
        tree[2 * id + 1] = power(lazy[id], r - mid);
        
        lazy[id] = 0;
    }
}

void build(int id, int l, int r) {
    lazy[id] = 0;
    if (l == r) {
        tree[id] = phi[a[l]];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);
    tree[id] = (tree[2 * id] * tree[2 * id + 1]) % MOD;
}

void update(int id, int l, int r, int u, int v, int val) {
    if (u > r || v < l) return;
    if (u <= l && r <= v) {
        lazy[id] = val;
        tree[id] = power(val, r - l + 1);
        return;
    }
    push(id, l, r);
    int mid = (l + r) / 2;
    update(2 * id, l, mid, u, v, val);
    update(2 * id + 1, mid + 1, r, u, v, val);
    tree[id] = (tree[2 * id] * tree[2 * id + 1]) % MOD;
}

long long query(int id, int l, int r, int u, int v) {
    if (u > r || v < l) return 1;
    if (u <= l && r <= v) return tree[id];
    push(id, l, r);
    int mid = (l + r) / 2;
    return (query(2 * id, l, mid, u, v) * query(2 * id + 1, mid + 1, r, u, v)) % MOD;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    freopen("GAME.INP", "r", stdin);
    freopen("GAME.OUT", "w", stdout);

    sang_phi();

    cin >> n >> q;

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

    build(1, 1, n);
    
    while (q--) {
        int type; cin >> type;

        if (type == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            update(1, 1, n, l, r, phi[x]);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << "\n";
        }
    }

    return 0;
}

# Bài 5: Dãy Số Quyền Năng

::::info
:::spoiler 💡 Hint 1
Để tính được độ mạnh $P_i$, ta cần tính $W(X)$ - số cách biểu diễn $X$ thành tổng các số nguyên tố liên tiếp. Vì $A_i \leq 10^5$, ta có thể dùng Sàng Eratosthenes và kỹ thuật mảng cộng dồn để tiền xử lý.
:::
::::

::::info
:::spoiler 💡 Hint 2
Với mỗi số $A_i$, ta nên tính trước giá trị độ mạnh thực tế $P_i = W(A_i) - K$. Bài toán trở thành tìm đoạn con có tổng lớn nhất sau khi loại bỏ tối đa $M$ phần tử.
:::
::::

## Subtask 1
:::: spoiler Solution ✅
* Duyệt mọi đoạn con $[l, r]$.
* Duy trì danh sách $M$ phần tử nhỏ nhất trong đoạn.
* Tổng cần tìm = (Tổng đoạn) - (Tổng các số âm thuộc danh sách $M$).
:::info
Độ phức tạp: $O(N^2 \cdot M \log M)$
:::
::::
::: spoiler Code 💻

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

#define Nexuron signed main
#define endl '\n'
#define ll long long

const int N = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;

int W[N];
vector<int> primes;
bool is_prime[N];
inline void sieve() {
    fill(is_prime, is_prime + N, true);
    for (int i = 2; i < N; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = (ll)i * i; j < N; j += i) {
                is_prime[j] = false;
            }
        }
    }
}
inline void precompute() {
    vector<ll> pre;
    pre.push_back(0);
    for (int p : primes) {
        pre.push_back(pre.back() + p);
    }
    int m = primes.size();
    for (int i = 0; i < m; i++) {
        for (int j = i; j < m; j++) {
            ll sum = pre[j+1] - pre[i];
            if (sum >= N) break;
            W[sum]++;
        }
    }
}
int n, m;
ll k, ans, P[N];
Nexuron() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    // freopen("main.INP", "r", stdin);
    // freopen("main.OUT", "w", stdout);
    sieve();
    precompute();
    cin >> n >> k >> m;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        P[i] = W[x] - k;
    }
    for (int l = 0; l < n; l++) {
        ll cur = 0;
        vector<ll> s;
        for (int r = l; r < n; r++) {
            cur += P[r];
            s.push_back(P[r]);
            sort(s.begin(), s.end());
            if ((int)s.size() > m) {
                s.pop_back();
            }
            ll tmp = cur, rm = 0;
            for (ll val : s) {
                if (val < 0) {
                    rm += val;
                    tmp = max(tmp, cur - rm);
                }
            }
            ans = max(ans, tmp);
        }
    }
    cout << ans;
    return 0;
}
    

:::

## Subtask 2
:::: spoiler Solution ✅
Khi $M = 0$, bài toán trở thành tìm đoạn con có tổng lớn nhất.

Ta dùng thuật toán Kadane:
* **cur**: tổng lớn nhất của đoạn con kết thúc tại vị trí hiện tại.
* **ans**: tổng lớn nhất tìm được trên toàn dãy.
* Ở mỗi bước, cập nhật `cur = max(P[i], cur + P[i])` và `ans = max(ans, cur)`.
:::info
Độ phức tạp thuật toán: $\mathcal{O}(N)$
:::
::::

::: spoiler Code 💻

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

#define Nexuron signed main
#define endl '\n'
#define ll long long

const int N = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;

int W[N];
vector<int> primes;
bool is_prime[N];
inline void sieve() {
    fill(is_prime, is_prime + N, true);
    for (int i = 2; i < N; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = (ll)i * i; j < N; j += i) {
                is_prime[j] = false;
            }
        }
    }
}
inline void precompute() {
    vector<ll> pre;
    pre.push_back(0);
    for (int p : primes) {
        pre.push_back(pre.back() + p);
    }
    int m = primes.size();
    for (int i = 0; i < m; i++) {
        for (int j = i; j < m; j++) {
            ll sum = pre[j+1] - pre[i];
            if (sum >= N) break;
            W[sum]++;
        }
    }
}
int n, m;
ll k, ans, P[N];
Nexuron() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    freopen("main.INP", "r", stdin);
    freopen("main.OUT", "w", stdout);
    sieve();
    precompute();
    cin >> n >> k >> m;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        P[i] = W[x] - k;
    }
    ll cur = 0, ans = 0; 
    for (int i = 0; i < n; i++) {
        cur = max(P[i], cur + P[i]);
        ans = max(ans, cur);
    }
    cout << ans;
    return 0;
}

:::

## Subtask 3
:::: spoiler Solution ✅
Sử dụng Quy hoạch động (DP):
* Gọi $dp[j]$ là tổng lớn nhất của đoạn con kết thúc tại vị trí hiện tại và đã xóa $j$ phần tử ($0 \le j \le M$).
* Với mỗi $P_i$, cập nhật:
* $dp[j] = \max(dp[j] + P_i, dp[j-1])$ (duyệt $j$ từ $M$ về $1$).
* $dp[0] = \max(P_i, dp[0] + P_i)$.
* Kết quả là giá trị lớn nhất của tất cả trạng thái $dp[0 \dots M]$ .
:::info
Độ phức tạp thuật toán: $\mathcal{O}(N \cdot M + N\log \log N)$
:::
::::
::: spoiler Code 💻

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

#define Nexuron signed main
#define endl '\n'
#define ll long long

const int N = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int W[N];
vector<int> primes;
bool is_prime[N];
inline void sieve() {
    fill(is_prime, is_prime + N, true);
    for (int i = 2; i < N; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = (ll)i * i; j < N; j += i) {
                is_prime[j] = false;
            }
        }
    }
}
inline void precompute() {
    vector<ll> pre;
    pre.push_back(0);
    for (int p : primes) {
        pre.push_back(pre.back() + p);
    }
    int m = primes.size();
    for (int i = 0; i < m; i++) {
        for (int j = i; j < m; j++) {
            ll sum = pre[j+1] - pre[i];
            if (sum >= N) break;
            W[sum]++;
        }
    }
}
int n, m;
ll dp[11];
ll k, ans;
Nexuron() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    freopen("main.INP", "r", stdin);
    freopen("main.OUT", "w", stdout);
    sieve();
    precompute();
    cin >> n >> k >> m;
    fill(dp, dp + m + 1, -INF);
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        // cerr << W[x] << " ";
        ll p = W[x] - k;
        for (int j = m; j >= 1; j--) {
            dp[j] = max(((dp[j] == -INF) ? -INF : dp[j] + p), dp[j-1]);
            ans = max(ans, dp[j]);
        }
        if (dp[0] == -INF) dp[0] = p;
        else dp[0] = max(p, dp[0] + p);
        ans = max(ans, dp[0]);
    }
    cout << ans << endl;
    return 0;
}