Link Sub: http://www.spoj.com/PTIT/problems/BCPTICH/
Người Gửi: Dương Lee
- Problem:
Rất nhiều số nguyên dương có thể được biểu diễn thành tổng của một dãy các số nguyên liên tiếp.
Ví dụ:
6 = 1 + 2 + 3
9 = 5 + 4 = 2 + 3 + 4
Tuy nhiên, số 8 thì lại không thể biểu diễn được như vậy. Bài toán đặt ra là với mỗi số nguyên cho trước, hãy đếm xem có thể có bao nhiêu cách biểu diễn số nguyên đó thành tổng của các số nguyên dương liên tiếp.
InputVí dụ:
6 = 1 + 2 + 3
9 = 5 + 4 = 2 + 3 + 4
Tuy nhiên, số 8 thì lại không thể biểu diễn được như vậy. Bài toán đặt ra là với mỗi số nguyên cho trước, hãy đếm xem có thể có bao nhiêu cách biểu diễn số nguyên đó thành tổng của các số nguyên dương liên tiếp.
Dòng đầu tiên ghi số bộ test, không lớn hơn 1000. Mỗi bộ test bao gồm thứ tự bộ test, tiếp theo là một số nguyên dương n nhỏ hơn 231
Output
Example:
Với mỗi bộ test, in ra màn hình thứ tự bộ test, tiếp theo là số cách biểu diễn tìm được
Input
7
1 6
2 9
3 8
4 1800
5 987654321
6 987654323
7 987654325
Output:
1 1
2 2
3 0
4 8
5 17
6 1
7 23
- Solution:
Ta có tổng dãy số liên tiếp của: 1, 2, 3, ... n có dạng = (1+n)(n-1+1)/2. Tổng quát hơn nó là: = (r+l)(r-l+1)/2; với: l, l+1, ... r;
Ta thấy rằng N = (r+l)(r-l+1)/2 <=> N*2 = (r+l)(r-l+1);
Coi
r+l = x;
r-l+1 = y;
=> 2*N = x*y => x, y là ước của 2*n (x, y nguyên).
-> Liệt kê các ước của 2*N;
Với mỗi ước thu được là x -> y=N/x; -> Giải hệ tìm được r, l; -> kiểm tra r, l xem có thỏa man không rồi đếm.
Ta thấy rằng N = (r+l)(r-l+1)/2 <=> N*2 = (r+l)(r-l+1);
Coi
r+l = x;
r-l+1 = y;
=> 2*N = x*y => x, y là ước của 2*n (x, y nguyên).
-> Liệt kê các ước của 2*N;
Với mỗi ước thu được là x -> y=N/x; -> Giải hệ tìm được r, l; -> kiểm tra r, l xem có thỏa man không rồi đếm.
- Code:
C++:
https://ideone.com/9OxHbu
#include <iostream>
#include <math.h>
using namespace std;
long long count (long long N)
{
long long d = 0;
long long c = sqrt(N);
long long l, r;
long long x, y;
for (long long i=2; i<=c; i++)
{
if (N%i==0)
{
x = N/i;
y = i;
if ((y+x-1)%2==0)
{
r = (y+x-1)/2;
l = x - r;
if (l>=1 && r>l)
d++;
}
}
}
return d;
}
int main ()
{
int t;
cin>>t;
int n;
long long X;
while (1)
{
if (t==0) break;
t--;
cin>>n;
cin>>X;
cout<<n<<" "<<count(2*X)<<endl;
}
return 0;
}JAVA:
...Python:
...