首页 > 代码库 > gym101102J Divisible Numbers(预处理)

gym101102J Divisible Numbers(预处理)

题意:

给你一个n(1e5)q(1e5)表示n个数的数列,q个询问,每次询问给你l(n),r(n),s(1023),

s表示一个二进制数列,当前位为1表示对应的这个位上的数出现,比如5表示101,即1和3出现,

l,r表示一段区间,这段区间中的每个数,只要能整除出现的数中的任意一个,就会对答案有1的贡献。

问每个询问的贡献。

思路:

由于出现了1就肯定每个数都有贡献(都是1的倍数),然后就可以少一位,用512表示9位出不出现的所有情况,

用n*512的复杂度预处理所有的情况,O(1)查询。

for(int j=2;j<=10;j++)
    if(x%j==0) s=s|(1<<(j-2));
for(int j=0;j<512;j++)
    sum[j][i]=sum[j][i-1]+((s&j)?1:0);

gym101102J Divisible Numbers(预处理)