首页 > 代码库 > 20140711 set
20140711 set
题目大意
维护一个可重集，支持：
插入一个正整数
询问一个正整数k，集合中有多少个数是k的倍数
数据范围是40000，时限0.5s
暴力肯定不行，想起这道题叫set，今天中午刚刚看了STL set用法，于是用了一个set来做，想着是logn的复杂度，其实还是n，总的就是n^2..............................................
后面才知道应该将插入的数分解因数，读入一个查询值直接输出即可,O(n*n^0.5)
1 #include<cstdio> 2 #include<string.h> 3 using namespace std; 4 5 int a[40000]; 6 7 int n; 8 9 int main()10 {11 freopen("set.in","r",stdin);12 freopen("set.out","w",stdout);13 int x,y;14 scanf("%d",&n);15 int ans=0;16 memset(a,0,sizeof(a));17 while (n--)18 {19 scanf("%d%d",&x,&y);20 if (x==1)21 {22 for (int i=1;i*i<=y;i++)23 {24 if(y%i==0)25 {26 a[i]++;27 a[y/i]++; 28 }29 if (y==i*i) a[i]--; 30 }31 }32 else33 {34 ans=ans xor a[y]; 35 }36 }37 printf("%d",ans);38 return 0;39 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。