# Solution #2: Bài 1 - HSG cấp THPT tỉnh Trà Vinh (2024-2025)
**Tác giả: Phan Thành Hưng (hungg_261)**

___

## Đề bài

**Tóm tắt đề:**
Mỗi màn chơi xuất hiện khối lập phương có cạnh tăng dần từ $1$ đến $N$. Để tiêu diệt khối lập phương cạnh $a$ cần tiêu hao $a^3$ năng lượng. Người chơi phải tiêu diệt tuần tự từ cạnh $1$ đến $N$ mới chiến thắng.
Nhiệm vụ của bạn là tính tổng năng lượng cần để tiêu diệt từ khối cạnh $1$ đến $N$.

Ràng buộc: $0 < N \le 10^{16}$.

## Lời giải

> *Do áp dụng thuật toán vét cạn cho bài này là rất đơn giản nên mình sẽ không nhắc tới ở đây.*

Chắc hẳn hầu hết các bạn đều đã rất quen thuộc với công thức sau:
$$ f(n)=1^3 + 2^3 + ... +\ n^3 = (1+2+...+\ n)^2=\left( \frac{n(n+1)}{2}\right)^2 $$

Vậy lời giải chính là $f(n) \mod n$. Vấn đề lớn ở đây là giá trị của $n(n+1)$ có thể vượt ra ngoài phạm vi biểu diễn của `long long`, dẫn đến tràn số. Do vậy ta cần phải xử lý một cách khéo léo như sau.

Trước hết ta đưa về bài toán tính: $$M=\frac ab\ \textnormal{mod}\ m$$
với $\frac ab \in \mathbb{Z}$.

Viết lại biểu thức, ta cần phải tính:
$$ M=\frac ab - m \cdot \left\lfloor \frac{\frac ab}{m} \right\rfloor$$
$$= \frac ab - m \cdot \left\lfloor \frac{a}{bm} \right\rfloor $$
nhân cả 2 vế với $b$ ta được:
$$ b \cdot M= \frac ab \cdot b - bm \cdot \left\lfloor \frac{a}{bm} \right\rfloor $$
$$ = a-bm \cdot \left\lfloor \frac{a}{bm} \right\rfloor$$
Có thể thấy lúc này tương đương với:
$$ b \cdot M=a\ \textnormal{mod}\ (bm)$$
$$ \Rightarrow M=\frac{a\ \textnormal{mod}\ (bm)}b$$
Vậy ta chỉ cần tính như công thức trên là được. Có thể thấy lúc này nếu tìm được số $a'$ sao cho $a \equiv a'\ (\textnormal{mod}\ m)$ thì:
$$ M=\frac{a\ \textnormal{mod}\ (bm)}b = \frac{a'\ \textnormal{mod}\ (bm)}b$$

Mà nếu $a$ là tích của nhiều số thì ta có thể áp dụng tính chất đồng dư của phép nhân:
$$ \Rightarrow a=uv \equiv a'=(u\ \textnormal{mod}\ m) \times (v\ \textnormal{mod}\ m)\quad\quad (\textnormal{mod}\ m)$$

Do đó công thức cuối cùng của bài là:
$$ \left(\frac{n(n+1)\ \textnormal{mod}\ (2\times MOD)}{2} \right)^2 \ \textnormal{mod}\ MOD$$

___

### Code tham khảo
**Code (C++):**

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

const int MOD=1e8;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int N;
    cin>>N;
    
    N %= MOD;
    int ans=(N*(N+1) % (2*MOD))/2 % MOD;
    
    cout<<(ans*ans %MOD)<<'\n';
    return 0;
}

### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(1)$
- Độ phức tạp không gian: $O(1)$

## Tổng kết
Đây là một bài khá đơn giản và dùng để tránh liệt, đặc biệt là đối với THPT. Riêng khúc lấy dư cần phải xử lý khéo léo một chút để tránh tràn số. Hi vọng mọi người thấy lời giải của mình hữu ích :Đ. **Bye bye!**