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
AC × 59
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