Submission #3144664
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define REP(i, n) for(int i=0; i<(n); ++i) #define FOR(i, a, b) for(int i=(a); i<(b); ++i) #define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i) #define DEBUG(x) cout<<#x<<": "<<x<<'\n' #define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n' #define ALL(a) (a).begin(), (a).end() #define CHMIN(a, b) a=min((a), (b)) #define CHMAX(a, b) a=max((a), (b)) const ll MOD=1000000007ll; // const ll MOD=998244353ll; #define FIX(a) ((a)%MOD+MOD)%MOD const double EPS=1e-11; #define EQ0(x) (abs((x))<EPS) #define EQ(a, b) (abs((a)-(b))<EPS) const int MAX_N=1e6; bool is_prime_small[MAX_N+1]; int cnt[MAX_N+1]; int num[MAX_N+1]; int segment_sieve(int a, int b){ for(ll i=2; i*i<b; ++i){ is_prime_small[i]=true; } REP(i, b-a){ num[i]=i+a; } for(int i=2; i*i<b; ++i){ if(is_prime_small[i]){ for(ll j=2*i; j*j<b; j+=i){ is_prime_small[j]=false; } ll tmp=i; while(tmp<b){ for(ll j=max(2ll, (a+tmp-1)/tmp)*tmp; j<b; j+=tmp){ ++cnt[j-a]; num[j-a]/=i; } tmp*=i; } } } int res=0; REP(i, b-a){ if(num[i]!=1){ ++cnt[i]; } if(is_prime_small[cnt[i]]){ ++res; } } return res; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int l, r; cin>>l>>r; cout<<segment_sieve(l, r+1)<<'\n'; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Prime-Factor Prime |
User | izumo |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1564 Byte |
Status | AC |
Exec Time | 24 ms |
Memory | 8448 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 00_sample_05, 10_small_00, 10_small_01, 10_small_02, 10_small_03, 10_small_04, 10_small_05, 10_small_06, 10_small_07, 10_small_08, 10_small_09, 20_medium_00, 20_medium_01, 20_medium_02, 20_medium_03, 20_medium_04, 20_medium_05, 20_medium_06, 20_medium_07, 20_medium_08, 20_medium_09, 30_medium_00, 30_medium_01, 30_medium_02, 30_medium_03, 30_medium_04, 30_medium_05, 30_medium_06, 30_medium_07, 30_medium_08, 30_medium_09, 40_one_00, 40_one_01, 40_one_02, 50_large_low_00, 50_large_low_01, 50_large_low_02, 50_large_low_03, 50_large_low_04, 60_large_high_00, 60_large_high_01, 60_large_high_02, 60_large_high_03, 60_large_high_04, 70_max_low_00, 70_max_low_01, 70_max_low_02, 70_max_low_03, 70_max_low_04, 80_max_high_00, 80_max_high_01, 80_max_high_02, 80_max_high_03, 80_max_high_04 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 2 ms | 4352 KB |
00_sample_01 | AC | 2 ms | 4352 KB |
00_sample_02 | AC | 3 ms | 6656 KB |
00_sample_03 | AC | 2 ms | 4352 KB |
00_sample_04 | AC | 4 ms | 6784 KB |
00_sample_05 | AC | 23 ms | 8448 KB |
10_small_00 | AC | 2 ms | 4352 KB |
10_small_01 | AC | 2 ms | 4352 KB |
10_small_02 | AC | 1 ms | 4352 KB |
10_small_03 | AC | 2 ms | 4352 KB |
10_small_04 | AC | 2 ms | 4352 KB |
10_small_05 | AC | 1 ms | 4352 KB |
10_small_06 | AC | 2 ms | 4352 KB |
10_small_07 | AC | 1 ms | 4352 KB |
10_small_08 | AC | 2 ms | 4352 KB |
10_small_09 | AC | 2 ms | 4352 KB |
20_medium_00 | AC | 5 ms | 7040 KB |
20_medium_01 | AC | 16 ms | 8448 KB |
20_medium_02 | AC | 13 ms | 8448 KB |
20_medium_03 | AC | 8 ms | 7552 KB |
20_medium_04 | AC | 15 ms | 8448 KB |
20_medium_05 | AC | 11 ms | 8192 KB |
20_medium_06 | AC | 19 ms | 8448 KB |
20_medium_07 | AC | 8 ms | 7424 KB |
20_medium_08 | AC | 18 ms | 8448 KB |
20_medium_09 | AC | 4 ms | 6784 KB |
30_medium_00 | AC | 19 ms | 8448 KB |
30_medium_01 | AC | 10 ms | 7936 KB |
30_medium_02 | AC | 14 ms | 8448 KB |
30_medium_03 | AC | 12 ms | 8448 KB |
30_medium_04 | AC | 18 ms | 8448 KB |
30_medium_05 | AC | 13 ms | 8448 KB |
30_medium_06 | AC | 14 ms | 8448 KB |
30_medium_07 | AC | 6 ms | 7040 KB |
30_medium_08 | AC | 7 ms | 7296 KB |
30_medium_09 | AC | 17 ms | 8448 KB |
40_one_00 | AC | 2 ms | 4352 KB |
40_one_01 | AC | 2 ms | 4352 KB |
40_one_02 | AC | 2 ms | 4352 KB |
50_large_low_00 | AC | 22 ms | 8448 KB |
50_large_low_01 | AC | 22 ms | 8448 KB |
50_large_low_02 | AC | 22 ms | 8448 KB |
50_large_low_03 | AC | 23 ms | 8448 KB |
50_large_low_04 | AC | 23 ms | 8448 KB |
60_large_high_00 | AC | 23 ms | 8448 KB |
60_large_high_01 | AC | 22 ms | 8448 KB |
60_large_high_02 | AC | 22 ms | 8448 KB |
60_large_high_03 | AC | 22 ms | 8448 KB |
60_large_high_04 | AC | 22 ms | 8448 KB |
70_max_low_00 | AC | 22 ms | 8448 KB |
70_max_low_01 | AC | 23 ms | 8448 KB |
70_max_low_02 | AC | 23 ms | 8448 KB |
70_max_low_03 | AC | 23 ms | 8448 KB |
70_max_low_04 | AC | 24 ms | 8448 KB |
80_max_high_00 | AC | 23 ms | 8448 KB |
80_max_high_01 | AC | 23 ms | 8448 KB |
80_max_high_02 | AC | 23 ms | 8448 KB |
80_max_high_03 | AC | 23 ms | 8448 KB |
80_max_high_04 | AC | 23 ms | 8448 KB |