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?????
Sauce?
Соус?! О.о
Педобира, уроженца форчана, удивляет слово соус?
please write in english ......
kk. What is source of your problem?
its a codechef problem.............
Link please.
http://www.codechef.com/APRIL12/problems/DUMPLING
use Inclusion-exclusion_principle
Note,
A
divisble byB
andC
A
divisible bylcm(B,C)
Что ж, не будем разочаровывать паренька, что в этой задаче ему ответ на его вопрос абсолютно не поможет:)
Try this with
sz=6,
but I'm not sure about my code :D.Complexity: O(22sz) — about 212 operations with sz = 6 :(
can u please tell the logic behind your code. else i would not be able to understand it