Số đặc biệt

Trong quá trình nghiên cứu, giáo sư X phát hiện ra một loại số nguyên mới và đặt tên nó là số đặc biệt, một số nguyên dương n được gọi là số đặc biệt nếu nó thỏa mãn hai tính chất sau:
1) n chia hết cho 3
2) n có đúng 9 ước.
Giáo sư X muốn khảo sát mật độ các số đặc biệt nên nhờ các bạn tham gia thi chọn HSG Tin học cấp tỉnh lập trình giải quyết bài toán sau: “Cho hai số nguyên không âm a, b. Hãy đếm số lượng số đặc biệt trong đoạn [a, b]”.
Dữ liệu cho trong tệp văn bản SDB.INP gồm:

• Dòng thứ nhất ghi số nguyên dương T là số bộ dữ liệu.
• T dòng sau, mỗi dòng chứa hai số nguyên dương a, b (a <= b). Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.

Các số ghi trên một dòng được cách nhau bởi dấu cách.
Kết quả ghi ra tệp văn bản SDB.OUT gồm T dòng, mỗi dòng là số lượng số đậc biệt trong đoạn [a, b] tương ứng với bộ dữ liệu
Ví dụ:

Giới hạn:

• Có 25% test ứng với 25% số điểm thỏa mãn a,  b <= 10³;    T = 1;
• Có 25% test ứng với 25% số điểm thỏa mãn a, b  < = 10⁴;    T <= 100;
• Có 25% test ứng với 25% số điểm thỏa mãn a,  b <= 10⁶;    T= 10;
• Có 25% test ứng với 25% số điểm thỏa mãn a,  b <= 10⁶;    T <= 10⁵.

Ý tưởng thuật toán:

Cách 1: Viết hàm đếm số ước của một số nguyên dương n: souoc(n)

• d=2;
• Với mỗi x chạy từ 2 đến sqrt(n):

o Nếu n mod x = 0 thì

• d=d+1;
• y = n/x;
• Nếu y ≠ x thì d=d+1;
• Trả về d;

Xử lí chính:

• Nhập t;
• Với mỗi i chạy từ 1 đến t:

* Nhập a, b;
* dem=0；
* Với mỗi n chạy từ a đến b:
* Neu n mod 3 = 0 và souoc(n)=9 thì tăng dem;
o Viết dem;
Cách 2:
Nhận xét: Nếu x là ước của N thì y=N/x cũng là ước
Số ước của N là lẻ ⇒ N là số chính phương;
a ≤ N => a ≤ x² => a – 1 < x² =>\sqrt{a-1}< x => \sqrt{a-1} + 1 ≤ x
Đoạn xử lí chính ở trên viết lại như sau:

• Nhập t;
• Với mỗi i chạy từ 1 đến t:

* Nhập a, b;
* dem=0；
* Với mỗi x chạy từ \sqrt{a-1} + 1 đến  \sqrt{b}
* Nếu x chia hết cho 3 và souoc(x*x)=9 thì tăng dem;
* Viết dem;
Cách 3 :
Ý tưởng: Tính mảng U[1..10⁶]: U[x] là số ước của x. Để tính nhanh thì dùng sàng ước;
Mảng D[1..10⁶]: D[x]=1 nếu x là số đặc biệt, còn không thì D[x]=0； (cách tính: Nếu x chia hết cho 3 và U[x]=9 thì D[x]=1)
Với mỗi a, b: ⇒ Đếm số 1 trong đoạn D[a..b] ⇔ Tính tổng đoạn D[a..b] = để tính nhanh, ta dùng mảng cộng dồn.

Code C++:

 

#include <bits/stdc++.h>
using namespace std; 
const int N = 1e6+5;
const int mod = 1e9+7;
int cnt[N]={}; 
int a[N];
bool check (int x)
{
	if (x %3 != 0) return false; 
	return (cnt [x] ==8);
}

void sang()
{
	for(int i=1;i <= N; i++)
 		for(int j = i*2 ; j <= N; j += i) ++cnt[j];
}
void process()
{
sang();
for (int i = 1; i<= N; i++)
{
	a[i] += a [i-1];
	a[i] += check (i);
}

int t, x, y;
cin >> t;
while (t--)
{
cin >> x >> y;
cout << a[y]-a[x-1] << '\n';
}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen ("SDB.inp", "r", stdin);
	freopen("SDB.out", "w", stdout);
	process() ;
	return 0;
}