# Hướng dẫn
Phân tích n thành tổng ít nhất 2 số nguyên liên tiếp đồng nghĩa với đếm số cặp **(l, r)** thoả mãn:
**(r - l + 1) * (r + l) = 2 * n.** \
Đặt **a = r - l + 1, b = r + l (a < b)**. \
⇒ **l = (b - a + 1) / 2** \
⇒ **r = (b + a - 1) / 2** \
Nhận thấy a, b là ước số của 2 * n nên ta chỉ cần duyệt qua các ước số của 2 * n và kiểm tra xem có
thoả mãn đồng thời cả 2 điều kiện:
- **(b - a + 1) % 2 == 0**
- **(b + a - 1) % 2 == 0** \
Hay không.
**Code**
```
#include <iostream>
using namespace std;
long long n;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
n *= 2;
int res = 0;
for (long long i=2; i*i<=n; ++i)
if (n % i == 0)
{
if (n/i == i) continue;
long long a = i;
long long b = n/i;
res += ((b - a + 1) % 2 == 0 && (b + a - 1) % 2 == 0);
}
return cout << res, 0;
}
```
# Giải :
mình sẽ giải bài này theo toán học
vì ta cần tìm số lần tổng các số liên tiếp bằng n mà tổng các số liên tiếp bằng n ta có thể thấy
giống như bài toán cấp số cộng với d = 1 và U1 là một số chưa biết mà theo bài tổng các số nguyên
dương khi đó ta có thể nhận ra U1 cũng phải nguyên dương mà U1 + (U1+d) + ... + (U1+(k-1)d) = n với
k là số lượng của các phần tử liên tiếp ta có thể gộp biểu thức trên thành kU1 + ((k-1)k)/2 = n
có thể bạn chưa biết n(n+1)/2 là tổng các số liên tiếp từ 1 đến n tương tự như trên thì ((k-1)k)/2
là tổng các số liên tiếp từ 1 đến k-1, ta có n không đổi và U1 là số nguyên dương bất kì vậy ta chỉ
cần đếm số lần số k thoả mãn kU1 + ((k-1)k)/2 = n và U1 là số nguyên dương là ra kết quả của bài toán
rồi, vậy ta cần đếm k từ đâu và khi nào dừng lại. Ta bắt đầu k tại 2 vì bài yêu cầu ít nhất là 2 số
liên tiếp cộng với nhau và kết thúc tại ((1+8n)-1)/2 vì ta cần tìm hết tất cả số k mà bài bắt là tìm
tổng liên tiếp các số nguyên dương khi đó ta có ((L+1)L)/2 = n với L là số lớn nhất mà tổng số lượng
từ 1 đến L nhỏ hơn hoặc bằng n vì L là giá trị lớn nhất có thể thoả mãn nên ta sẽ cho k kết thúc tại
đó và khi ta khai triển ((L+1)L)/2 = n ra thì ta sẽ được L^2 + L - 2n = 0 một phương trình bậc 2
và ((1+8n)-1)/2 là 1 trong 2 nghiệm của phương trình và nó luôn dương vì k là số nguyên dương.
# CODE :
```Python
n = int(input())
L = round(((1+8*n)**0.5-1)/2)
s = 0
for k in range(2,L+1):
bt = (n-((k-1)*k)//2)/k
if int(bt) == bt:
s += 1
print(s)
```
**Ý TƯỞNG CHÍNH**:
Số cách viết $n$ thành tổng của ít nhất hai số nguyên dương liên tiếp cũng chính là số cặp $(i, j)$ nguyên dương, $i < j$ thỏa:
$i + (i + 1) + (i + 2) + \dots + j = n$
$\iff \frac{(j + i)(j - i + 1)}{2} = n$
$\iff (j + i)(j - i + 1) = 2n$
Đến đây dễ thấy $j + i$ và $j - i + 1$ là cặp ước lớn và ước nhỏ của $2n$.
**MỘT SỐ NHẬN XÉT ĐỂ TỐI ƯU**:
Hiển nhiên trường hợp ước nhỏ $j - i + 1 = 1 (\iff i = j)$ không thỏa do $i < j$.
Quan trọng hơn, thay vì thử từng cặp ước lớn và ước nhỏ để giải ra $i$ và $j$, ta nhận thấy $j + i$ và $j - i + 1$ là cặp ước khác tính chẵn lẻ của $2n$:
> Trường hợp $j + i = j - i + 1 = \sqrt{2n}$ (nếu $2n$ chính phương) do đó cũng không thỏa.
> Với mọi cặp ước lớn và ước nhỏ còn lại, nếu đã thỏa mãn khác tính chẵn lẻ thì chắc chắn sẽ giải được $i$ và $j$ thỏa mãn (Bạn đọc tự chứng minh).
Tóm lại, ta chỉ cần duyệt trong khoảng $(1, \sqrt{2n})$ và đếm các ước nhỏ khác tính chẵn lẻ với ước lớn tương ứng rồi cộng vào kết quả. Độ phức tạp vẫn là $O(\sqrt n)$ nhưng thời gian được cải thiện do không cần thực hiện giải hay kiểm tra $i$ và $j$.
hungkm466
Created at
20 likes
Chinhle
Created at
8 likes
sasaki2c
Created at
1 likes