SPOJ.COM - Thuật toán bài CUBEFR - Cube Free Numbers

Đề bài:

"Cube free number" là một số mà không có số chia nào của nó là số dạng lập phương (số dạng lập phương ví dụ như 8 (222)), 27(333). Do đó những số cube free number là 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18,...(ta xem xét 1 như là số cube free number). 8, 16, 24, 27, 32 không phải 8, 16, 24, 27, 32. Trong đó, vị trí của 1 trong dãy là 1, vị trí của 2 là 2, vị trí của 3 là 3, vị trí của 10 là 9. Cho trước một số dương, bạn hãy cho biết xem nó có phải là cube free number hay không, và nếu có thì chỉ ra vị trí của nó trong dãy.

Đầu vào

Dòng đầu tiên là là số T, số lượng test case, 1 <= T <= 100000. Sau đó là T dòng. Mỗi dòng là một số nguyên dương n, 1 <= n <= 1000000.

Đầu ra

Với mỗi test case, in ra một dòng dạng "Case I:", trong đó i là chỉ số của test case. Sau đó nếu nó không phải là cube free number thì in ra "Not Cube Free". Ngược lại thì in ra vị trí của nó trong dãy.

Ví dụ

Đầu vào:

10
1
2
3
4
5
6
7
8
9
10

Đầu ra:

Case 1: 1
Case 2: 2
Case 3: 3
Case 4: 4
Case 5: 5
Case 6: 6
Case 7: 7
Case 8: Not Cube Free
Case 9: 8
Case 10: 9

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/CUBEFR/

Phân tích

• Mình sẽ sử dụng thuật toán tham lam Greedy để giải bài toán. Cụ thể hơn là sử dụng thuật toán sàng. Bởi lẽ dãy số chỉ có một, nên mình sẽ sinh ra dãy số một lần duy nhất.

• Trước tiên, dùng một mảng đánh dấu, khởi tạo giá trị bằng 0. Duyệt các số i từ 2 đến 100, khi đó số dạng lập phương từ số đó là k = i*i*i. Suy ra số 1*k, 2*k, 3*k, ... sẽ không phải là cube free number và được đánh dấu -1. Ở đây, mình chỉ xét đến 100 vì 100*100*100 = 1000000, là đủ đến giá trị lớn nhất của n.

• Sau khi đánh dấu những số không phải cube free number, mình sẽ duyệt một lượt nữa để đếm vị trí của những số cube free number và lưu luôn vào mảng đánh dấu trên.

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<stdio.h>

const int MAX = 1000001;
int free_cube[MAX];

void create_free_cube()
{
	for(int i = 2; i <= 100; i++)
	{
		int t = i*i*i;
		int j = 1;

		while(true)
		{
			int temp = t*j;
			if(temp < MAX)
			{
				free_cube[temp] = -1;
				j++;
			}
			else break;
		}
	}

	int cnt = 0;
	for(int i = 1; i < MAX; i++)
		if(free_cube[i] > -1)
		{
			cnt++;
			free_cube[i] = cnt;
		}
}

int main()
{
	int T = 0;
	scanf("%d",&T);

	for(int i = 0; i < MAX; i++)
	    free_cube[i] = 0;

	create_free_cube();

	for(int tc = 0; tc < T; tc++)
	{
		int n = 0;
		scanf("%d",&n);

		if(free_cube[n] == -1) printf("Case %d: Not Cube Free\n",tc+1);
		else printf("Case %d: %d\n",tc+1,free_cube[n]);
	}
	return 0;
}