Đếm số(tổng hợp)

Xem dạng PDF
Gửi bài giải
Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Yêu cầu:

Cho 1 dãy số nguyên gồm ~n~ số cho trước. Hãy đếm tất cả các số chính phương, nguyên tố, hoàn hảo, phong phú, T-prime trong đoạn từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Giải thích:

  • Ước thực sự của 1 số là tập hợp tất cả các ước dương nhỏ hơn nó.
  • Số chính phương là số có căn bậc 2 của nó là một số nguyên.
  • Số nguyên tố là số chỉ có 2 ước là 1 và chính nó.
  • Số hoàn hảo là số có tổng các ước thực sự của nó bằng chính nó. Ví dụ, số 6 có tổng các ước số (không kể 6) là 1 + 2 + 3 = 6. Do đó 6 là một số hoàn hảo.
  • Số phong phú là số có tổng các ước thực sự của số đó lớn hơn số đó. Ví dụ, số 12 có tổng các ước số (không kể 12) là 1 + 2 + 3 + 4 + 6 = 16 > 12. Do đó 12 là một số phong phú.
  • Số T-prime là số có đúng 3 ước.

Input:

  • Dòng 1: Ghi số nguyên ~𝑛~, (~1 \le n \le 10^5~).
  • Dòng 2: Ghi ~𝑛~ số nguyên ~A_1, A_2,...,A_n, 1 \le A_i \le 10^6~
  • Dòng 3: Ghi số nguyên dương ~q~ - số bộ test.
  • ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương ~x~, ~y~ (~1 \le x \le y \le n~; ~1 \le q \le 10^5~)

Output:

  • Gồm q dòng: Ứng với mỗi cặp số x,y in ra 5 số nguyên dương lần lượt là số lượng các số chính phương, nguyên tố, hoàn hảo, phong phú, t-prime tìm được trong đoạn từ ~x~ đến ~y~.

Example:

Input:

7
2 3 5 7 12 8 6
2
1 3
2 4

Output:

0 3 0 0 0
0 3 0 0 0

Bình luận

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


  • 4
    hello  đã bình luận lúc 10, Tháng 3, 2026, 13:10

    include<bits/stdc++.h>

    using namespace std;

    define ll long long

    define f ios::syncwithstdio(0);cin.tie(0);cout.tie(0)

    define file(name) freopen(name ".inp","r",stdin);freopen(name ".out","w",stdout)

    define TIME (1.0 * clock() / CLOCKSPERSEC)

    define time cerr << '\n' << "Time elapsed: " << TIME << " s.\n"; return 0;

    define lcm(a,b) ((a)*(b))/__gcd(a,b)

    define u unsigned

    define pb push_back

    define endl '\n'

    const int N=1e6+5;

    vector<bool>nt(N,1),tprime(N,0); vector<int>pp(N,0); set<int>hh={6,28,496,8128};

    void sang(){ nt[0]=nt[1]=0; for(int i=2;ii<N;i++) if(nt[i])for(int j=ii;j<N;j+=i)nt[j]=0; for(int i=2;ii<N;i++) if(nt[i]) tprime[ii]=1; for(int i=1;i<N;i++) for(int j=i*2;j<N;j+=i) pp[j]+=i; for(int i=1;i<N;i++) pp[i]=(pp[i]>i); }

    int main(){ f; sang();

    int n;cin>>n;
vector<int>precp(n+1),prent(n+1),prehh(n+1),prepp(n+1),pretnt(n+1);

for(int i=1;i<=n;i++){
    int x;cin>>x;
    ll t=sqrt(x);

    precp[i]=precp[i-1]+(t*t==x);    
    prent[i]=prent[i-1]+nt[x];      
    prehh[i]=prehh[i-1]+hh.count(x); 
    prepp[i]=prepp[i-1]+pp[x];       
    pretnt[i]=pretnt[i-1]+tprime[x];
}

int q;cin>>q;
while(q--){
    int x,y;cin>>x>>y;
    cout<&lt;precp[y]-precp[x-1]<<" "<&lt;prent[y]-prent[x-1]<<" "<&lt;prehh[y]-prehh[x-1]<<" "<&lt;prepp[y]-prepp[x-1]<<" "<&lt;pretnt[y]-pretnt[x-1]<<endl;
}

    }