首页 > 代码库 > bzoj 3529 数表

bzoj 3529 数表

2024-08-19 18:05:23   225人阅读

题目链接：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 数表


联系
我们