Bedao Regular Contest 03 - PRIME

Xem dạng PDF
Gửi bài giải
Điểm: 0,13 (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
    trinhphucvanlong  đã bình luận lúc 14, Tháng 6, 2026, 4:24

    include <bits/stdc++.h>

    using namespace std;

    define ALL(a) a.begin(),a.end()

    define pll pair<long long,long long>

    define llu long long unsigned

    define vlong vector<long long>

    const int maxn=1e6+5; int q,a,b,k,p[maxn],s[8][maxn]; void sieve(){ for(int i=2;i<maxn;i++){ if(p[i]==0){ for(int j=i;j<maxn;j+=i){ p[j]++; } } } for(int k=1;k<8;k++){ for(int j=2;j<maxn;j++){ s[k][j] = s[k][j-1]+(p[j] == k ? 1:0); } } } signed main() { iosbase::syncwith_stdio(false); cin.tie(NULL); sieve(); cin>>q; while(q--){ cin>>a>>b>>k; cout<<s[k][b]-s[k][a-1]<<"\n"; } return 0; } /* nhap

    */


  • -4
    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;
    }
}