SPOJ.COM - Thuật toán bài AFS - Amazing Factor Sequence

Đề bài:

Thái là bạn cùng lớp với Học - người rất giỏi về lập trình và đã tạo ra dãy số nguyên tố rất hay. Thái cảm thấy ghen tị với Học nên quyết định tạo nên dãy số cho riêng mình. Bởi vì anh ấy không quá sáng tạo, nên đã tạo ra một dãy với định nghĩa tương tự như của Học, chỉ khác ở f(n), cụ thể là:

• a[0] = a[1] = 0;

• Với n > 1, a[n] = a[n-1] + f(n), trong đó, f(n) là tổng các số nguyên dương ở tập S

• Với S = {x | x < n và n % x = 0}

Bây giờ, Học đã yêu cầu Thái lập trình để tìm ra f(n) - như Thái đã định nghĩa. Do đó, Thái mong muốn sự giúp đỡ của bạn bởi vì anh ta không biết về lập trình. Nhiệm vụ của bạn đơn giản là tìm a[n] với số n cho trước (n < 10^6)

Đầu vào

Bạn được cho nhiều test case. Dòng đầu tiên bao gồm số T (T <= 100), tổng số test case. T dòng tiếp theo chứa một số nguyên dương duy nhất N với 1 < N < 10^6.

Đầu ra

Mỗi test case, in ra một dòng duy nhất là số a[n], được định nghĩa như trên.

Ví dụ

Đầu vào:

3 
3 
4 
5 

Đầu ra:

2 
5 
6 

Giải thích:

f(2) = 1 {1} 
f(3) = 1 {1} 
f(4) = 3 {1, 2} 
f(5) = 1 {1} 

Do đó:

a[2] = a[1] + f[2] = 0 + 1 = 1; 
a[3] = a[2] + f[3] = 1 + 1 = 2; 
a[4] = a[3] + f[4] = 2 + 3 = 5; 
a[5] = a[4] + f[5] = 5 + 1 = 6; 

Bạn có thể tham khảo đề bài tiếng anh và submit tại đây: http://www.spoj.com/problems/AFS/

Phân tích

Ở đây ta có thể áp dụng đúng công thức để tính cho mỗi test case. Tuy nhiên, như vậy sẽ dẫn đến việc phải lập lại quá trình tính toán rất nhiều. Điều này sẽ dẫn đến time limit.

Khi đó thuật toán ta phải dùng là thuật toán quy hoạch động - Dynamic programming. Đối với những bài toán kiểu này, ta sẽ tính toán một lần và lưu kết quả đó vào một mảng. Như vậy, ta chỉ cần tính toán một lần. Và với mỗi test case chỉ in ra kết quả.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include<iostream>
using namespace std;

typedef unsigned long long ull;

const ull MAX = 1000005;

ull a[MAX];            // Lưu mảng a
ull f[MAX];            // Lưu mảng f

void CreateArray()
{
    for(ull i = 0; i < MAX; i++)
        a[i] = f[i] = 0;

    // Tạo mảng f
    for(ull k = 1; k < MAX; k++)
    {
        // Cập nhật cho tất cả các số j có ước số là k
        for(ull j = k*2; j < MAX; j += k)
            f[j] += k;
    }

    // Tạo mảng a
    for(ull i = 2; i < MAX; i++)
        a[i] = a[i-1] + f[i];
}

int main()
{
    ios::sync_with_stdio(false);

    // comment dòng này trước khi submit
    freopen("input.txt","r",stdin);

    CreateArray();

    ull T;
    cin >> T;

    for(ull tc = 0; tc < T; tc++)
    {
        ull n;
        cin >> n;
        cout << a[n] << endl;
    }

    return 0;
}