Hướng dẫn cho Phân tích số


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: jumptozero

Mình xin chia sẻ lời giải bài này như sau: Giả sử số \(n\) đã cho phân tích thành tổng của \(k\) số: \(u_0,u_1,u_2,...,u_k\)
Trong đó:

  • \(u_0=a\), với \(a\) là số nguyên dương bất kỳ

  • \(u_{i}=u_{i-1}+1\) với \(1\le i\le k\).

Nên từ đây ta suy ra được: \(u_k = a + k\)

Khi đó ta có: \(u_0+u_1+...+u_k = a + (a+1)+...+(a+k) = (k+1)a + \frac{k(k+1)}{2}\) (do \(0+1+2+...+k = \frac{k(k+1)}{2}\))

Do đó ta sẽ có: \((k+1)a+\frac{k(k+1)}{2}=n\implies 2(k+1)a+k^2+k=2n \implies a = \frac{2n-k-k^2}{2(k+1)}\)

\(a\in \mathbb{N}^*\) nên \(\frac{2n-k-k^2}{2(k+1)} \in \mathbb{N}^*\)

Do đó ta phải có hai điều sau:

  • \(2n-k-k^2>0(1)\)

  • \(2n-k-k^2 \vdots 2(k+1)(2)\)

Từ \((1)\) ta có: $k^2+k-2n<0\iff 4k^2+4k-8n<0 \iff (2k+1)^2<8n+1 \iff k\le \left \lfloor {\frac{\sqrt{8n+1}-1}{2}}\right \rfloor $

\(n \sim 10^{16} \implies k \sim 10^8\)

Do đó ta chỉ cần cho một vòng for từ \(\left \lfloor {\frac{\sqrt{8n+1}-1}{2}}\right \rfloor\) trở về \(1\) nếu số \(k\) nào thoả mãn \((1),(2)\) thì số đó chính là số cần tìm !

Nếu không tìm được số nào thoả mãn thì ta in ra \(0\)

Ps: Nếu cố gắng hết sức mà vẫn chưa ra thì bạn có thể tham khảo tại đây



Bình luận

Không có bình luận nào.