Блог пользователя triploblastic

codeforces round #226 prob C
Автор triploblastic, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First mistake is that MAX is too small

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
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]

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится 
     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

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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..

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

wrong post place

→ Ответить