2284
1403
Bài 7. Số ước nguyên tố
Tên file: uocnto.py hoặc uocnto.cpp
Hãy đếm trong đoạn [a, b] các số nguyên dương thỏa mãn yêu cầu: số lượng các ước của nó là một số nguyên tố.
Input: uocnto.inp
• Dòng 1: chứa số T là số lượng các đoạn cần đếm
• Dòng 2: T dòng tiếp theo, mỗi dòng chứa một cặp số nguyên a và b
Output: uocnto.out
• Gồm T dòng, mỗi dòng là kết quả tương ứng với input
Ví dụ:
Uocnto.inp
2
25
1 100
Uocnto.out
4
32
Ràng buộc
•
Subtask1: có 30% số điểm 1 ≤ a ≤ b ≤ 200 và T ≤ 100
Subtask2: có 30% số điểm 1 ≤ a ≤ b ≤ 2000 và T ≤ 1000
Subtask3: có 40% còn lại 1 ≤ a ≤ b ≤ 106 và T ≤ 105
•
•
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
727
333
#include <bits/stdc++.h>
#define N int(1e6+1)
using namespace std;
int nt[N], c[N];
void sangnt()
{
fill(nt+1,nt+N+1,1);
fill(c+1,c+N+1,1);
nt[1] = c[1] = 0;
for (int i=2; i*i<=N; i++)
if (nt[i]==1)
for (int j=i*i; j<=N; j+=i)
nt[j] = c[j] = 0;
}
int demuoc(int x)
{
int souoc = 1, i = 2;
while (i*i <= x)
{
int d = 0;
while (x % i == 0)
{
d++;
x = x/i;
}
souoc *= 2*d + 1;
i++;
}
if (x > 1) souoc *= 3;
return souoc;
}
void init()
{
sangnt();
for (int i=2; i*i<=N; i++)
{
int k = demuoc(i);
if (nt[k])
c[i*i] = 1;
}
for (int i=1; i<=N; i++)
c[i] += c[i-1];
}
int main()
{
freopen("uocnto.inp","r",stdin);
freopen("uocnto.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
init();
int t;
cin >> t;
while (t--)
{
int a, b;
cin >> a >> b;
cout << c[b] - c[a-1] << '\n';
}
return 0;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
Bảng tin