rum3r's blog

By rum3r, history, 4 weeks ago, In English

Cananyone explain me the DP solution of this problem??

Why we are using DP? Why this solution isn't giving correct Answer?

###

What's the complexity of the solution that I have written I know for sieve it's O(N*log(logN)). But I have modified that.

const int maxN = 2e5 + 9;
bool prime[maxN];
int cnt[maxN];
void sieve(){
	for(int i=2; i<=maxN; ++i){
		prime[i] = 1;
		cnt[i] = 0;
	}
	prime[0] = prime[1] = 0;
	for(ll i=2; i*i<=maxN; ++i){
		if(prime[i]){
			cnt[i] = 1;
			//incrementing all the multiples of primes by 1..
			for(int j=2*i; j<=maxN; j+=i){
//				dbg3(i, j, cnt[j]);
				prime[j] = 0;
				cnt[j]++;
			}
		}
	}
	//incrementing all primes after root N by 1.. 
	for(int i=sqrt(maxN); i<=maxN; ++i){
		if(prime[i]){
			cnt[i] =1;
		}
	}
	
}

PROBLEM

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

we are using dp because then for various test cases we did not need to transverse from a to b to count number having k primes..

we can compute an array by modification in sieve at once then we can maintain a dp[n][k] where k=1,2,3,4,5 ex. dp[n][1]=count of 1 primes up to n ... dp[n][2]=count of 2 primes up to n ..

then we can simply take difference of k primes up to b and a-1 that is dp[b][k]-dp[a-1][k]

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your explanation is quite helpful. Appreciate the effort!

    Is there any mathematical proof for this that a number can only have 5 prime divisors atmost??

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      bro check your question

      k is up to 5 only constraint..

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks!! You really helped a lot!

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Bro I got AC. 0.01s? Can you tell me complexity? How it's blazing fast?? AC I swear this is the last one :)