Editorial for Bedao Regular Contest 03 - PRIME
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Thuật toán trâu
Với mỗi số ~n~ từ ~a~ đến ~b~, ta xét tất cả các ước của ~n~ rồi kiểm tra số đó có phải nguyên tố hay không.
Thuật toán tối ưu hơn:
Một số ~n~ có ~k~ ước nguyên tố khác nhau đồng nghĩa với trong cách phân tích thừa số nguyên tố của ~n~, có đủ ~k~ thừa số nguyên tố. Ví dụ ~20~ có ~2~ ước thừa số nguyên tố khác nhau ~(20 = 2 \times 2 \times 5, 2~ ước nguyên tố là ~2~ và ~5)~.
Đến đây thì ta sử dụng sàng nguyên tố để phân tích thừa số nguyên tố, sử dụng kĩ thuật Prefix Sum để trả lời mỗi truy vấn trong ~O(1)~ với đoạn ~[L,R]~
Code mẫu
#include <iostream> #include <stdio.h> #include <vector> #include <cmath> #include <math.h> #include <map> #include <algorithm> #include <set> #include <bitset> #include <queue> #include <cstring> #include <stack> #include <iomanip> #include <assert.h> #define BIT(x,pos) (((x)>>(pos)) & 1LL) #define _(x) (1LL<<(x)) #define bitCnt(x) __builtin_popcountll(x) #define turnOn(x,pos) ((x) = (_(pos))) #define turnOff(x,pos) ((x) &= ~(_(pos))) #define flipBit(x,pos) ((x) ^= (_(pos))) #define lowBit(x) ((x) & (-x)) #define turnAll(x) (_(x)-1LL) #define name "test" #define nameTask "" #define fastIO ios::sync_with_stdio(false); cin.tie(0); using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<int,ll> pil; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; const int N = 1E6; int f[8][N+9]; int cnt[N+9]; bool ck[N+9]; void sieve() { for (int i = 2;i <= N; ++i) if (ck[i] == 0) for (int j = 2*i;j <= N; j += i) { ck[j] = 1; cnt[j]++; } ck[1] = ck[0] = 1; for (int i = 1;i <= N; ++i) if (ck[i] == 0) cnt[i] = 1; for (int k = 1;k <= 7; ++k) for (int j = 1;j <= N; ++j) f[k][j] = f[k][j-1] + (cnt[j] == k); } int main() { fastIO sieve(); int q; cin>>q; while (q--) { int l, r, k; cin>>l>>r>>k; cout<<f[k][r] - f[k][l-1]<<"\n"; } }
Comments