首页 > 代码库 > 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(预处理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。