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

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

suppose we are given a number 'N' and we want to count all integers >=1 and <=N that are divisible by 'A' or 'B' or 'C' and 'D' or 'E' or 'F' then the code for this would be:

int ans=0;
for(int i=1;i<=N;i++)
  if((i%A==0 || i%B==0 || i%C==0) && (i%D==0 || i%E==0 || i%F==0))
      ans++;

cout<<ans;

the above code would run in O(N) time; but suppose 'N' is too big then is there any faster way to accomplish the above task?????

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

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

Sauce?

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

please write in english ......

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

use Inclusion-exclusion_principle

Note, A divisble by B and C A divisible by lcm(B,C)

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

Что ж, не будем разочаровывать паренька, что в этой задаче ему ответ на его вопрос абсолютно не поможет:)

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

Try this with sz=6, but I'm not sure about my code :D.
Complexity: O(22sz) — about 212 operations with sz = 6 :(

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

    can u please tell the logic behind your code. else i would not be able to understand it