triploblastic's blog

codeforces round #226 prob C
By triploblastic, 11 years ago, In English

can someone tell me what is wrong with my code? i first generated all the primes up to sqrt(10^7) and then for every prime, counted how many number are divided by it...

5797193

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First mistake is that MAX is too small

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
while(X[i] % prime[j] == 0)
      X[i] /= prime[j];

I do not understand why you do it. You just need to determine whether X[i] is divisible by prime[j] but not the power of prime[j] in X[i]

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
     while(j < prime.SZ) {
      if(X[i] < prime[j])
        break;
      if(X[i] % prime[j] == 0) {
        prime_cnt[j]++;
        while(X[i] % prime[j] == 0)
          X[i] /= prime[j];
      }

      j++;
    }

    also need to reduce x[i],and reduce "while" working time,but it is not enough to passed

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i figured this inner loop will run 20 times max for each X[i] cause 2^20 ~ 10^7, the limit for each number...so this should be 10^6 * 20 ~ 2*10^7... but i cant figure out why did it get WA in #test case 6..

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should use primes bigger than sqrt(10^7) too. Why did you just get rid of them?

        → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

wrong post place

→ Reply