Cho dãy số vô hạn sau: 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,... Cho 2 số A và B viết chương trình tính tổng các số trong dãy từ A đến B INPUT: 1 3 --> OUTPUT: 5 INPUT: 3 7 --> OUTPUT: 15

Ý tưởng

Ta giả sử dãy cần tính tổng của chúng ta như sau:

x + x + ... + x + ((x+1) + ... + (x+1)) + ((x+2) + ... + (x+2)) + ... + ((x+y-1) + ... + (x+y-1)) + ((x + y) + (x + y) + ... + (x+y))

Có b - a + 1 số hạng trong phép tính trên

Dễ thấy, ta luôn có x + 1 số x+1, x+2 số x+2, ..., x+y-1 số x+y-1

Gọi số số x là u, số số (x+y) là v. Vậy ta có thể viết lại biểu thức trên bằng cách:

x * u + (x+1) ^ 2 + (x+2)^2 + ... + (x+y-1)^2 + (x+y)*v

Ta sẽ tách biểu thức trên thành 3 phần:

- Phần đầu: x*u

- Phần thứ 2: (x+1) ^ 2 + (x+2)^2 + ... + (x+y-1)^2

- Phần thứ 3: (x+y)*v

Xử lý phần 1 và phần 3

Mình sẽ lấy phần 1 ra làm ví dụ

Để tính phần 1, ta cần phải tính x và tính u

Vậy tính x như thế nào? Ta để ý: Có tất cả 1 + 2 + 3 + ... + n số trước số có giá trị n + 1 đầu tiên của dãy. Gọi tổng 1 + 2 + 3 + ... + n là sum1(n). Sử dụng công thức, ta có sum1(n) = n*(n+1)/2.

Vậy ta cần tìm giá trị x sao cho sum1(x) >= a và sum1(x-1) < a. 

=> Tìm kiếm nhị phân để tìm ra x

Khi ta đã có được giá trị của x, ta có thể dễ dàng tìm được u. Làm thế nào? 

Do có sum1(n) các số trước số có giá trị n+1 đầu tiên và a - 1 số trước số có thứ tự a

=> u = sum1(x) - (a-1) = sum1(x) - a + 1

Vậy phần 1 đã được giải quyết

Phần 3 cũng tương tự, ta cũng tìm được (x+y), và rút ra được công thức v = b - sum1(y-1)

Xử lý phần 2

Ta thấy, phần 2 là tổng 1 dãy các số chính phương

Ta nhớ lại công thức tính sum2(n) = 1^2 + 2^2 + ... + n^2 = (n*(n+1)/2) + ((n-1)*n*(n+1)/3)

Mình sẽ để link cách chứng minh bên dưới

Vậy chẳng phải x^2 + (x+1)^2 + ... + y^2 = sum2(y) - sum2(x-1) sao?

Phần 2 đã được giải quyết

Cộng tất cả các kết quả của 3 phần lại, ta sẽ được đáp án cần tìm

Chú ý: Trường hợp đặc biệt

Nếu giá trị của x bằng giá trị của y, khi đó cách làm của chúng ta sẽ không còn đúng nữa

Vậy phải làm như thế nào?

Ta thấy nếu x = y thì tất cả các số trong khoảng a->b của dãy sẽ bằng x

Vậy ta sẽ in ra trực tiếp kết quả là x * (b-a+1)

Code

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

// ll la long long (dong thu 2)
// Dung so lon de tranh bi tran so
ll a,b,lb,rb,lbs,rbs,ms;

ll sum1(ll n){
    // Ham tim tong cac so tu 1 toi n
    // Su dung cong thuc
    return (n*(n+1))/2;
}

ll sum2(ll n){
    // Tinh 1^2 + 2^2 + ... + n^2
    // Su dung cong thuc
    return (n*(n+1)/2) + ((n-1)*n*(n+1)/3);
}

ll getCurrent(ll x){
    // Ham tim xem so thu x la so nao
    // Su dung tim kiem nhi phan
    ll left = 1,right = 1e9, mid, sumx = sum1(x);
    while(left <= right){
        mid = (left + right)/2;
        if(sum1(mid-1) < x && x <= sum1(mid)) return mid;
        if(sum1(mid) < x) left = mid+1;
        else if(sum1(mid-1) >= x) right = mid-1;
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> a >> b;
    lb = getCurrent(a); rb = getCurrent(b);
    if(lb == rb){
        // Truong hop dac biet neu so thu a bang so thu b
        cout << lb * (b-a+1);
        return 0;
    }
    // Tong ben trai
    lbs = lb * (sum1(lb) - a + 1);
    // Tong ben phai
    rbs = rb * (b - sum1(rb-1));
    // Tong o giua
    ms = sum2(rb-1) - sum2(lb);
    // cout << rb - lb > 1 << '\n';
    cout << lbs + rbs + ms;
    return 0;
}