Bedao Regular Contest 03 - PRIME - VNOJ: VNOI Online Judge

Bedao Regular Contest 03 - PRIME

Điểm: 0,40 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

bedao

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hãy đếm số lượng số trong đoạn từ ~a~ đến ~b~ có ~k~ ước nguyên tố khác nhau. Cho ~Q~ truy vấn , mỗi truy vấn gồm ba số nguyên dương ~a, b, k~.

Input

Dòng đầu tiên chứa số nguyên dương ~Q~ là số lượng truy vấn. ~(1 \leq Q \leq 10^5)~
~Q~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~a_i, b_i, k_i~ lần lượt mô tả các giá trị như trong yêu cầu bên trên. ~(1 \le a \le b \le 10^6, 1 \le k \le 7)~

Output

Ứng với truy vấn thứ ~i~, in ra một số nguyên duy nhất là số lượng số trong đoạn ~a_i~ đến ~b_i~ mà có ~k_i~ ước nguyên tố khác nhau. Mỗi truy vấn in ra trên một dòng.

Sample Input

2
3 6 2
7 10 1

Sample Output

1
3

Subtask

~40\%~ số test có ~Q, a, b \le 10^3~
~60\%~ số test còn lại không có điều kiện gì thêm

Bình luận

Hãy đọc nội quy trước khi bình luận.

-1

ngoccaidu2008 đã bình luận lúc 22, Tháng 10, 2025, 15:58

#include <bits/stdc++.h>
using namespace std;
#define __Hormer_Nguyen__ signed main()
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
const int maxn=5+1e6;
int q,a,b,k,p[maxn],s[8][maxn];
bool f[maxn];
void sang()
{
    memset(f,true,sizeof f);
    f[0]=f[1]=false;
    for (int i=2;i<=sqrt(maxn);i++)
    {
        for (int j=i*i;j<=maxn;j+=i) f[j]=false;
    }for (int i=2;i<=maxn;i++)
    {
        if (f[i])
        {
            for (int j=i;j<=maxn;j+=i) p[j]++;
        }
    }for (int i=1;i<=7;i++)
    {
        for (int j=2;j<=maxn;j++)
        {
            s[i][j]=s[i][j-1];
            if (p[j]==i)
            {
                s[i][j]=s[i][j-1]+1;
            }
        }
    }
}
__Hormer_Nguyen__
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    sang();
    cin>>q;
    while (q--)
    {
        cin>>a>>b>>k;
        cout<<s[k][b]-s[k][a-1]<<endl;
    }
}