codeforces round #226 prob C

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

Автор triploblastic, 13 лет назад, По-английски

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

triploblastic
13 лет назад
7

Комментарии (7)

Написать комментарий?

tacklemore

13 лет назад, скрыть # |

First mistake is that MAX is too small

→ Ответить

tacklemore

13 лет назад, скрыть # |

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]

→ Ответить

LashaBukhnikashvili

13 лет назад, скрыть # ^ |

← Rev. 2 →

 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

→ Ответить

triploblastic

13 лет назад, скрыть # ^ |

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

→ Ответить