首页 > 代码库 > bzoj 3529 数表
bzoj 3529 数表
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3529
题目大意:令F(i)为i的约数和,多次询问对于1<=x<=n,1<=y<=m,F(gcd(x,y))<=a的所有数对(x,y),求ΣF(gcd(x,y))%(2^31)
n,m<=10^5,a<=10^9
首先如果不考虑a的限制 令g(i)为1<=x<=n,1<=y<=m,gcd(x,y)=i的数的个数
那么显然有
利用线性筛处理出F(i) 那么答案显然是
治好了我多年的公式恐惧症。。。
现在我们只需要求出的前缀和 这个问题就能在O(√n)的时间内出解
枚举每一个i 枚举i的倍数 暴力即可求出这个函数 然后处理前缀和即可 复杂度是O(nlogn)的
那么现在有了a的限制怎么搞呢?
我们发现对答案有贡献的i只有F(i)<=a的i 那么我们将询问按照a从小到大排序 将F(i)从小到大排序 每次询问将<=a的F(i)按照之前的方式暴力插入 用树状数组来维护这个前缀和
这题就搞出来了
时间复杂度O(nlog^2n+q√nlogn) 有点卡。。。取模那里自然溢出int就行了 最后再对2147483647取一下&即可
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 7 using namespace std; 8 const int mod=2147483648; 9 const int maxn=100010; 10 11 int n,m,a; 12 int prime[maxn]; 13 int cnt; 14 int vis[maxn]; 15 int mu[maxn]; 16 int sum[maxn]; 17 18 struct node 19 { 20 int n,m,a,id; 21 }q[maxn]; 22 23 bool cmp2(node x,node y) 24 { 25 return x.a<y.a; 26 } 27 28 struct Node 29 { 30 int g; 31 int sum; 32 }f[maxn]; 33 34 bool cmp1(Node a,Node b) 35 { 36 return a.sum<b.sum; 37 } 38 39 long long ans[maxn]; 40 long long c[maxn]; 41 int lowbit(int x) 42 { 43 return x&-x; 44 } 45 46 void add(int x,int d) 47 { 48 while(x<maxn) 49 { 50 c[x]+=d; 51 x+=lowbit(x); 52 } 53 } 54 55 long long Sum(int x) 56 { 57 long long ans=0; 58 while(x>0) 59 { 60 ans += c[x]; 61 x -= lowbit(x); 62 } 63 return ans; 64 } 65 66 void init() 67 { 68 memset(vis,0,sizeof(vis)); 69 memset(f,0,sizeof(f)); 70 cnt=0; 71 mu[1]=1; 72 for(int i=2;i<maxn;i++) 73 { 74 if(!vis[i]) 75 { 76 prime[cnt++]=i; 77 mu[i]=-1; 78 } 79 for(int j=0;j<cnt&&i*prime[j]<maxn;j++) 80 { 81 vis[i*prime[j]]=1; 82 if(i%prime[j]) 83 mu[i*prime[j]]=-mu[i]; 84 else 85 { 86 mu[i*prime[j]]=0; 87 break; 88 } 89 } 90 } 91 sum[0]=0; 92 for(int i=1;i<maxn;i++) 93 sum[i]=sum[i-1]+mu[i]; 94 for(int i=1;i<maxn;i++) 95 for(int j=i;j<maxn;j+=i) 96 f[j].sum += i; 97 for(int i=1;i<maxn;i++) 98 f[i].g=i; 99 sort(f+1,f+maxn,cmp1); 100 } 101 102 long long cal(int n,int m) 103 { 104 if(n>m) 105 swap(n,m); 106 long long res=0; 107 int last=0; 108 for(int i=1;i<=n;i=last+1) 109 { 110 last=min(n/(n/i),m/(m/i)); 111 res += (long long)(n/i)*(m/i)*(Sum(last)-Sum(i-1)); 112 } 113 return res; 114 } 115 116 int main() 117 { 118 init(); 119 int T; 120 scanf("%d",&T); 121 for(int i=1;i<=T;i++) 122 { 123 scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a); 124 q[i].id=i; 125 } 126 sort(q+1,q+1+T,cmp2); 127 memset(c,0,sizeof(c)); 128 int j=1; 129 for(int i=1;i<=T;i++) 130 { 131 while(j<maxn&&f[j].sum<=q[i].a) 132 { 133 int g=f[j].g; 134 for(int k=g;k<maxn;k+=g) 135 add(k,f[j].sum*mu[k/g]); 136 j++; 137 } 138 ans[q[i].id]=cal(q[i].n,q[i].m); 139 } 140 for(int i=1;i<=T;i++) 141 printf("%lld\n",ans[i]%mod); 142 return 0; 143 }
bzoj 3529 数表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。