red_coder's blog

By red_coder, 14 years ago, In English

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

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

| Write comment?
»
14 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Sauce?

»
14 years ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

please write in english ......

»
14 years ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

use Inclusion-exclusion_principle

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

»
14 years ago, hide # |
Rev. 5  
Vote: I like it 0 Vote: I do not like it

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