Getting TLE

general
1

Problem Link :- KPRIME Problem - CodeChef

My Logic :- I have precomputed still getting TLE…

using namespace std;
using ll = long long;
int N = 10000000;
vector<int> sieve(N);

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MOD 1e9+7;


void init_code()
{
  fast_io;
  #ifndef ONLINE_JUDGE

  freopen("input.txt", "r", stdin);

  freopen("output.txt", "w", stdout);

  #endif // ONLINE_JUDGE
}

void createsieve()
{

	for(int i=1;i<=N;i++)
	{
		sieve[i] = i;
	}

	for(int i=2;i*i<=N;i++)
  	{
  		if(sieve[i] == i)
  		{
  			for(int j=i*i;j<=N;j+=i)
  			{
  				if(sieve[j] == j)
  				{
  					sieve[j] = i;
  				}
  			}
  		}
  	}
}

void solve()
{
	int a,b,k;
	cin>>a>>b>>k;

	vector<int> ans;
	int count = 0;
	for(int i=a;i<=b;i++)
	{
		int x = i;

		set<int> s;

		while(x != 1)
		{
			s.insert(sieve[x]);
			x = x/sieve[x];
		}

		if(s.size() == k)
		{
			count++;
		}
	}

	cout<<count<<"\n";
}

int main()
{
  init_code();
  createsieve();

  int t;
  cin>>t;

  while(t--)
  {
    solve();
  }

  return 0;
}```
2

Time complexity is O( T*(B-A)) , which in worst case would be 10^10 operation which will TLE , precalculate answer for x (1<=x<=100000) before answering the Test cases

3

Can u give me idea how can i precalculate x values

4

The same you are doing it for a to b , Just calculate count of no. Of prime factor for each no. from 1 to N , store it in an array , then create another array cnt[N][6] , where cnt[i][j] will store that how many no. between 1 and i have j prime factor , and then answer for each query will be cnt[b][k]-cnt [a-1][k]

1 Like
5

Implementation of @dhruv788’s approach:

using namespace std;

const ll N = 100001;
vector<ll> spf(N);
vector<vector<ll>> cnt_of_prime(N,vector<ll>(6,0));

void generate(){
    for(ll i=0;i<N;i++) spf[i] = i;
    for(ll i = 2;i*i<N;i++){
        if(spf[i] == i){
            for(ll j = i*i;j<N;j+=i){
                if(spf[j]==j) spf[j] = i;
            }
        }
    }
}
ll distinctPrime(ll a){
    unordered_set<ll> st;
    while(a!=1){
        st.insert(spf[a]);
        a = a/spf[a];
    }
    return st.size();
}
void generateResult(){
    //cout<<Prime(10)<<"\n";
    for(ll i = 2;i<N;i++){
        
        for(int j = 0;j<6;j++){
            cnt_of_prime[i][j] = cnt_of_prime[i-1][j];
        }
        ll cur = distinctPrime(i);
        if(cur<6){
            cnt_of_prime[i][cur]++;
        }
    }
}

void solve(){
    ll a,b,k;cin>>a>>b>>k;
    cout<<cnt_of_prime[b][k]-cnt_of_prime[a-1][k]<<"\n";
}
 
int main(){
ios_base::sync_with_stdio(false); 
cin.tie(NULL);
cout.tie(NULL);
generate();

generateResult();
TestCase
solve();
}
1 Like
6

Your generate functiom is wrong , you should have done if ( spf[ j ]!=j) spf[j]=i; in the loop of j

1 Like
7

But I got AC :stuck_out_tongue_winking_eye: :stuck_out_tongue_winking_eye:
submission

8

Great :joy: ( Maybe that is what matters )

9

Yesss… :stuck_out_tongue:

1 Like
10

@sudo_s @dhruv788

Bro I have some small doubts

(i) why j < 6 only why not other number…
(ii) i did not get why needed 2d array

11

We need 2d array to keep the count of numbers having j distinct prime factors from [1, i] (that’s why we used 6 because numbers having distinct prime count >= 6 can be ignored according to problem constraints. i.e 1<=k<=5)

P.S think of it as a prefix sum array.

1 Like
12

Got it Bro . Thanks

1 Like