Thuật toán

Chia sẻ đầy đủ về các thuật toán và lời giải các bài toán cơ bản

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;

Các 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:

(Các 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 tôi 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 tôi 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 các 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;
}

Code by Phạm Văn Lâm

108 views

3 bình luận

  1. Phạm Văn Lâm

    Trên đây là đề bài và lời giải bài AFS – Amazing Factor Sequence trên trang spoj.com. Rất mong nhận được sự ủng hộ và phản hồi từ các bạn.

    Trân trọng,
    Phạm Văn Lâm.

  2. Hoàng Lân

    anh có thể diễn giải ý tưởng làm thế nào để code f[n] như vậy không ạ?

    1. Phạm Văn Lâm

      * 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} => f(n) = tổng các ước số x của số n với x < n * Ví dụ: f(10): thì 10 có ước số ( < 10) là 1, 2, 5 => f[10] = 1 + 2 + 5 = 8.
      * Thử suy nghĩ ngược lại: bây giờ mình xét từng số x một, xem nó là ước số của số n nào thì cộng vào f[n].
      + Số 1 là ước số của mọi số, do đó ta sẽ cộng mọi số f[2], f[3],. … f[MAX] số 1.
      Bây giờ, ta có f[2] = 1, f[3] = 1, f[4] = 1,… f[MAX] = 1.
      + Tiếp theo, số 2 sẽ là ước số của 4, 6, 8, …. => ta sẽ cộng 2 vào các số chẵn
      Bây giờ, ta có f[2] = 1, f[3] = 1, f[4] = 1 + 2 = 3, f[5] = 1, f[6] = 1 + 2 = 3,…
      + Cứ xét như vậy cho đến hết là ta sẽ tính được mọi f[n]

      * Bạn có thể tham khảo thuật toán sàng số nguyên tố tại đây: https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes

Để lại bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *