Vì lời giải của bài này khá dài nên mình mong các bạn kiên trì để hiểu hơn bài toán này nhé

Mình sẽ chia lời giải gồm 2 phần:

• Phần 1: Gồm những định nghĩa, công thức và những bổ để cần dùng (kèm theo chứng minh )

• Phần 2: Ta sẽ áp dụng Phần 1 để giải quyết bài toán đề ra.

Phần 1: Định nghĩa, công thức và những bổ để cần dùng (kèm theo chứng minh)

• Ta định nghĩa \([P]=1\) nếu \(P=true\) và \([P]=0\) nếu \(P=false\). (\(P\) được hiểu ở đây là một mệnh đề) \(\rightarrow (I)\)

Xét một số nguyên dương \(n\) phân tích ra thừa số sẽ có dạng \(p_1^{a_1}.p_2^{a_2}.p_3^{a_3}...p_r^{a_r}\) với \(p_i(1\le i\le r)\) là các số nguyên tố.

Khi đó ta có các hàm số học kinh điển sau:

• Hàm Mobius \(\mu(n)\):

• \(\mu(1)=1\)

• \(\mu(n)=0\) nếu tồn tại \(a_i>1\)

• \(\mu(n)=(-1)^{r}\) nếu \(n=p_1.p_2....p_r\) hay \(a_i=1\) với mọi \(i=\overline{1,r}\)

• Hàm Phi Ơ-le (Euler's totient function):

• \(\phi(n)\) là số lượng số nguyên tố cùng nhau với \(N\) trong đoạn từ \(1\) đến \(N\)

• Công thức nghịch đảo Mobius (Mobius's inversion formula):

• \(\forall n\ge 1,g(n)=\sum\limits_{d|n}f(d)\implies f(n)=\sum\limits_{d|n}\mu(d)g(\frac{n}{d})\)

• Bổ đề 1: \(\sum\limits_{d|n}\phi(d)=n\)

Chứng minh:

Kí hiệu: \(S=\left\{1,2,...,n\right\}\)

\(\rightarrow\) Bây giờ ta sẽ phân hoạch tập \(S\) này thành các tập như sau:

• Với mỗi \(d\) là ước của \(n\), đặt \(A(d)=\left\{k\in S: gcd(k,n)=d\right\}\)

Khi đó ta có một nhận xét như sau:

• \(A(p)\cap A(q)=\emptyset\) với mọi \(p\ne q\) và \(p,q\) lần lượt là các ước của \(n\)

• \(\bigcup\limits_{d|n} A(d)=S\)

Nên từ đây ta suy ra được:

• \(\sum\limits_{d|n} |A(d)|=|S|=n\) (trong đó \(|X|\) - kí hiệu số lượng phần tử của tập \(X\)) \(\rightarrow (II)\)

Bây giờ ta sẽ đi tìm \(|A(d)|\).

Ta sẽ đi chứng minh: \(|A(d)|=\phi(\frac{n}{d})\)

Thật vậy, ta có: \(A(d)=\left\{k\in S: gcd(k,n)=d\right\}\iff A(d)=\left\{k\in S: gcd(\frac{k}{d},\frac{n}{d})=1\right\}\)

Đặt \(z=\frac{k}{d}\) khi đó ta có \(1\le z\le \frac{n}{d}\) (Vì \(1\le k\le n\))

Do đó \(|A(d)|\) chính bằng số lượng số \(z\in [1;\frac{n}{d}]\) và \(z\) nguyên tố cùng nhau với \(\frac{n}{d}\)

Nên từ đây ta suy ra được: \(|A(d)|=\phi(\frac{n}{d})\) (Theo định nghĩa của hàm Phi Ơ-le)

Từ \((II)\) ta suy ra được: \(n=\sum\limits_{d|n}|A(d)|=\sum\limits_{d|n}\phi(\frac{n}{d})=\sum\limits_{d|n}\phi(d)\)

Ps: Mình xin giải thích một chút vì sao : \(\sum\limits_{d|n}\phi(\frac{n}{d})=\sum\limits_{d|n}\phi(d)\) ? .

Đáp: Là bởi cả hai vế trái và phải chính bằng tổng các Phi Ơ-le của tất cả các ước của \(n\)

Như vậy là bổ đề 1 đã chứng minh hoàn tất !

• Bổ đề 2: \([n=1]=\sum\limits_{d|n}\mu(d)\)

Chứng minh:

• Với \(n=1\), theo \((I)\) ta có: \([n=1]=1\) và \(\sum\limits_{d|1}\mu(d)=\mu(1)=1\) Do đó bổ đề 2 hiển nhiên đúng vì cả vế trái và phải đều cùng bằng \(1\)

• Với \(n>1\), ta có \([n=1]=0\), do đó ta chỉ cần đi chứng minh \(\sum\limits_{d|n}\mu(d)=0\) là bài toán được giải quyết !

Thật vậy: Ta có: \(n=p_1^{a_1}.p_2^{a_2}.p_3^{a_3}...p_r^{a_r}\) với \(p_i\) là các số nguyên tố.

Khi đó xét một ước \(z\) bất kì của \(n\) sẽ thuộc một trong hai dạng sau:

• Dạng 1: \(z=p_\beta^{\gamma}.Q(Q\in \mathbb{N}^{*})\) với \(\beta\in \left\{1,2,...,r\right\}\) và \(\gamma\ge 2\). Khi đó \(\mu(z)=0\) (theo định nghĩa của hàm Mobius)

• Dạng 2: \(z\) không thuộc Dạng 1, tức là \(z\) sẽ là ước của \(n'=p_1p_2...p_r\).

Khi đó, ta có: \(\sum\limits_{d|n}\mu(d)=\sum\limits_{d|n'}\mu(d)=\mu(1)+\sum\limits_{1\le i\le r}\mu(p_i)+\sum\limits_{1\le i<j\le r}\mu(p_ip_j)+...+\mu(p_1p_2...p_r)=\binom{r}{0}1^{r}(-1)^0+\binom{r}{1}1^{r-1}(-1)^1+...+\binom{r}{r}1^0(-1)^{r}=(1-1)^0=0\) (Theo nhị thức Newton)

Như vậy việc chứng minh bổ đề 2 của ta đã hoàn tất!

• Bổ đề 3: \(\sum\limits_{d|n}d\mu(\frac{n}{d})=\phi(n)\)

Theo bổ đề 1, ta có: \(n=\sum\limits_{d|n}\phi(d)\), nên áp dụng công thức nghịch đảo mobius, trong đó: \(g(n)=n\) và \(f(n)=\phi(n)\), ta có:

Vì: \(g(n)=\sum\limits_{d|n}f(d)\implies f(n)=\sum\limits_{d|n}\mu(d)g(\frac{n}{d})\)

Hay ta có: \(\phi(n)=\sum\limits_{d|n}\mu(d).\frac{n}{d}=\sum\limits_{d|n}d\mu(\frac{n}{d})\)

Như vậy là bổ để 3 đã được chứng minh hoàn tất.

Chúng ta kết thúc phần 1, và chuyển sang phần 2. Sẽ còn nhiều phần hấp dẫn ở phần 2, các bạn tiếp tục đón xem nhé !

Phần 2: Giải quyết bài toán ban đầu.

Ta có: \(S=\sum\limits_{i=1}^{n}gcd( \left \lfloor {\sqrt[3]{i}} \right \rfloor,i)\)
\(=\sum\limits_{a=1}^{\left \lfloor {\sqrt[3]{n}} \right \rfloor}\sum\limits_{i=1}^{n}gcd(a,i).[\left \lfloor {\sqrt[3]{i}} \right \rfloor=a]\rightarrow (III)\)

Ta có: \(\left \lfloor {\sqrt[3]{i}} \right \rfloor=a \iff a\le \sqrt[3]{i}<a+1 \iff a^3\le i\le (a+1)^3-1\implies [\left \lfloor {\sqrt[3]{i}} \right \rfloor=a]=1 \iff a^3\le i\le (a+1)^3-1\)

Do đó ta suy ra được: \(\sum\limits_{i=1}^{n}gcd(a,i)[\left \lfloor {\sqrt[3]{i}} \right \rfloor=a]=\sum\limits_{i=a^3}^{min\left\{n,(a+1)^3-1\right\}}gcd(a,i)\)

Đặt \(r=\left \lfloor {\sqrt[3]{n}} \right \rfloor-1\)

Khi đó, từ \((III)\) ta suy ra được: \(S=\sum\limits_{a=1}^{\left \lfloor {\sqrt[3]{n}} \right \rfloor}\sum\limits_{i=a^3}^{min\left\{n,(a+1)^3-1\right\}}gcd(a,i)=S_1+S_2\), trong đó:

• \(S_1=\sum\limits_{a=1}^{r}\sum\limits_{i=a^3}^{min\left\{n,(a+1)^3-1\right\}}gcd(a,i)\)

• \(S_2=\sum\limits_{a=\left \lfloor {\sqrt[3]{n}} \right \rfloor}^{\left \lfloor {\sqrt[3]{n}} \right \rfloor}\sum\limits_{i=a^3}^{min\left\{n,(a+1)^3-1\right\}}gcd(a,i)\)

Tiếp theo, ta có 2 nhận xét quan trọng sau:

• Nhận xét 1: \(min\left\{n,(a+1)^3-1\right\}=(a+1)^3-1\) với mọi \(1\le a\le r\)

( Vì \((a+1)^3-1\le (r+1)^3-1 = (\left \lfloor {\sqrt[3]{n}} \right \rfloor-1+1)^3-1=(\left \lfloor {\sqrt[3]{n}} \right \rfloor)^3-1< n\))

• Nhận xét 2: \(min\left\{n,(a+1)^3-1\right\}=n\) với mọi \(a=\left \lfloor {\sqrt[3]{n}} \right \rfloor\)

( Vì ta có: \((a+1)^3 = (\left \lfloor {\sqrt[3]{n}} \right \rfloor+1)^3 \ge n+1 \implies (a+1)^3-1\ge n\) )

Từ đây ta suy ra được:

• \(S_1=\sum\limits_{a=1}^{r}\sum\limits_{i=a^3}^{min\left\{n,(a+1)^3-1\right\}}gcd(a,i)=\sum\limits_{a=1}^{r}\sum\limits_{i=a^3}^{(a+1)^3-1}gcd(a,i)\)

• \(S_2=\sum\limits_{a=\left \lfloor {\sqrt[3]{n}} \right \rfloor}^{\left \lfloor {\sqrt[3]{n}} \right \rfloor}\sum\limits_{i=a^3}^{n}gcd(a,i)=\sum\limits_{i=(\left \lfloor {\sqrt[3]{n}} \right \rfloor)^3}^{n}gcd(\left \lfloor {\sqrt[3]{n}} \right \rfloor,i)\)

Để tính được \(S_1,S_2\), ta đi xét một bài toán sau, đó chính là tính: \(Q=\sum\limits_{i=1}^{n}gcd(a,i)\)

Việc tính \(Q\) được thực hiện như sau:

• Ta có: \(Q=\sum\limits_{d}d\sum\limits_{i=1}^{n}[gcd(a,i)=d]=\sum\limits_{d}d\sum\limits_{i=1}^{n}[gcd(\frac{a}{d},\frac{i}{d})=1]\)

Đến đây áp dụng bổ đề 2 ở phần 1 ta có: \(Q=\sum\limits_{d}d\sum\limits_{i=1}^{n}\sum\limits_{t|gcd(\frac{a}{d},\frac{i}{d})}\mu(t)\)

Hay \(Q=\) \(\sum\limits_{d}d\sum\limits_{i=1}^{n}\sum\limits_{t|\frac{a}{d},t|\frac{i}{d}}\mu(t)\) = \(\sum\limits_{T|a}\left \lfloor {\frac{n}{T}} \right \rfloor \sum\limits_{d|T}d\mu(\frac{T}{d})\) \(\rightarrow (IV)\)

Đến đây, ta lại tiếp tục áp dụng bổ đề 3 ở phần 1 ta được:

\(Q=\sum\limits_{T|a}\left \lfloor {\frac{n}{T}} \right \rfloor \phi(T)\)

Hay \(Q=\) \(\sum\limits_{i=1}^{n}gcd(a,i)=\sum\limits_{T|a}\left \lfloor {\frac{n}{T}} \right \rfloor \phi(T)\) \(\rightarrow (V)\)

Mình nghĩ đây là một kết quả quan trọng và áp dụng được vào trong nhiều bài tương tự, các bạn nhớ lưu tâm chỗ này nhé !

• Bây giờ ta sẽ áp dụng kết quả \((V)\) này để tính \(S_1,S_2\) . Các bạn tiếp tục đón xem nhé !

Việc tính toán \(S_2\) hoàn toàn tương tự \(S_1\), nên mình chỉ trình bày phần \(S_1\) nhé, còn \(S_2\) dành cho các bạn đọc nhé !

Phần tính toán \(S_1\) như sau:

Ta có: \(S_1=\sum\limits_{a=1}^{r}\sum\limits_{a^3}^{(a+1)^3-1}gcd(a,i)=\sum\limits_{a=1}^{r}\sum\limits_{T|a}(\left \lfloor {\frac{(a+1)^3-1}{T}} \right \rfloor-\left \lfloor {\frac{a^3-1}{T}} \right \rfloor)\phi(T)\)

Đặt \(a=bT (b\in \mathbb{N}^{*})\)

\(\implies S_1=\sum\limits_{bT=1}^{r}\sum\limits_{T|bT}(\left \lfloor {\frac{(bT+1)^3-1}{T}} \right \rfloor-\left \lfloor {\frac{(bT)^3-1}{T}} \right \rfloor)\phi(T)\)

\(=\sum\limits_{T}\phi(T)\sum\limits_{b=1}^{\left \lfloor {\frac{r}{T}} \right \rfloor}(\left \lfloor {\frac{(bT+1)^3-1}{T}} \right \rfloor-\left \lfloor {\frac{(bT)^3-1}{T}} \right \rfloor)\)

Để hiểu được vì sao có phép biến đổi này, các bạn cứ nháp từng ví dụ nhỏ ra là thấy nhé, phần này mình xin dành cho bạn đọc:

Mặt khác ta lại có: \(\left \lfloor {\frac{(bT+1)^3-1}{T}} \right \rfloor-\left \lfloor {\frac{(bT)^3-1}{T}} \right \rfloor = \left \lfloor {b^3T^2+3b^2T+3b} \right \rfloor-\left \lfloor {b^3T^2-\frac{1}{T}} \right \rfloor\)

\(=(b^3T^2+3b^2T+3b)-(b^3T^2-1)=3b^2T+3b+1\)

Nên từ đây ta suy ra được: \(S_1=\sum\limits_{T=1}^{r}\phi(T)[(3T\sum\limits_{b=1}^{\left \lfloor {\frac{r}{T}} \right \rceil}b^2)+(3\sum\limits_{b=1}^{\left \lfloor {\frac{r}{T}} \right \rceil}b)+\left \lfloor {\frac{r}{T}} \right \rceil]\)

Đến đây, ta áp dụng thêm 2 đẳng thức quen thuộc: \(\sum\limits_{i=1}^{q}i^2=\frac{q(q+1)(2q+1)}{6}\) và \(\sum\limits_{i=1}^{q}i=\frac{q(q+1)}{2}\) nữa là \(S_1\) đã được giải quyết hoàn tất.

Như vậy là bài toán đã giải quyết xong.

\(\rightarrow\) Tiếp theo là đến phần code.

• Ta nhận thấy rằng, khi đã tìm được công thức, để phần code được tối ưu, chúng ta nên tính trước các giá trị của hàm Phi - Ơ le và biểu thức \(Q\).

• Để tính phần nguyên căn bậc 3 của một số nguyên dương \(n\) bất kỳ, các bạn nên dùng chặt nhị phân nhé !

• Về phần xử lý mod, các bạn chú ý tính trước các giá trị \(6^{-1} \text{%} 998244353\) và \(2^{-1} \text{%} 998244353\) (Để tính được cái này các bạn dùng Inverse mod và luỹ thừa nhị phân nhé)

• Độ phức tạp của bài này là \(O(r)\sim O(\sqrt[3]{n})\sim 10^{7}\).

Như vậy là solution cho bài toán đã hoàn tất, mình hy vọng qua bài này, các bạn học thêm được một chút gì đó và rất cảm ơn tất cả các bạn đọc hết phần solution này !

Các bạn có thể tham khảo code tại đây

Ps: Nếu có gì khó hiểu hoặc thắc mắ, các bạn cứ comment nhé !