首页 > 代码库 > BZOJ 3529: [Sdoi2014]数表 [莫比乌斯反演 树状数组]
BZOJ 3529: [Sdoi2014]数表 [莫比乌斯反演 树状数组]
3529: [Sdoi2014]数表
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 1399 Solved: 694
[Submit][Status][Discuss]
Description
有一张N×m的数表，其第i行第j列（1 < =i < =礼，1 < =j < =m）的数值为
能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。
Input
输入包含多组数据。
输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。
Output
对每组数据，输出一行一个整数，表示答案模2^31的值。
Sample Input
2
4 4 3
10 10 5
4 4 3
10 10 5
Sample Output
20
148
148
HINT
1 < =N．m < =10^5 ， 1 < =Q < =2×10^4
Source
Round 1 Day 1
一个位置的答案就是gcd(i,j)的约数和
一个个单独算不好优化不行，从gcd(i,j)的取值方面考虑
设F(i)为i的约数和，f(i)为gcd(x,y)=i的个数，那么答案就是ΣF(i)*f(i)
f(i)上两题用到过，反演后f(i)=Σ{i|d} miu(d/i)*(n/d)*(m/d)
d和i的取值范围相同，可以得到如下式子
现在我们只需要求出g(i)=
F(i)是约数和函数，可以通过线性筛计算，或者直接nlogn暴力枚举倍数，速度差不多
然后和上一题一样，暴力枚举每个i更新它的倍数
那么a的限制如何处理？考虑离线
我们发现对答案有贡献的i只有F(i)<=a的i 那么我们将询问按照a从小到大排序 将F(i)从小到大排序 每次询问将<=a的F(i)按照枚举倍数更新的方式插入 用树状数组来维护g的前缀和 这样枚举倍数logn，每个倍数插入树状数组logn，总共nlog^2n
本题取模有一种好厉害的做法：自然溢出int,最后&0x7FFFFFFF
复杂度O(nlog^2n+q√nlogn)
注意:排序[1,N)的话是sort(a+1,a+N),不要a+N+1.......
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=1e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}struct ques{ int n,m,a,id; bool operator <(const ques &r)const{return a<r.a;}}q[N];int n,m;int notp[N],p[N],mu[N],minfac[N],t1[N],t2[N];struct data{ int s,i; bool operator <(const data &r)const{return s<r.s;}}sf[N];void sieve(){ for(int i=1;i<N;i++) sf[i].i=i; mu[1]=1; sf[1].s=1; for(int i=2;i<N;i++){ if(!notp[i]){ p[++p[0]]=i,mu[i]=-1; minfac[i]=i; sf[i].s=i+1; t1[i]=i+1; t2[i]=i; } for(int j=1,k;j<=p[0]&&(k=i*p[j])<N;j++){ notp[i*p[j]]=1; minfac[k]=p[j]; if(i%p[j]==0){ mu[i*p[j]]=0; t2[k]=t2[i]*p[j]; t1[k]=t1[i]+t2[k]; sf[k].s=sf[i].s/t1[i]*t1[k]; break; } mu[i*p[j]]=-mu[i]; t1[k]=1+p[j]; t2[k]=p[j]; sf[k].s=sf[i].s*sf[p[j]].s; } }}int g[N];inline int lowbit(int x){return x&-x;}inline void add(int p,int v){for(int i=p;i<N;i+=lowbit(i)) g[i]+=v;}inline int sum(int p){ int ret=0; for(int i=p;i;i-=lowbit(i)) ret+=g[i]; return ret;}void ins(int x){ for(int d=sf[x].i;d<N;d+=sf[x].i) add(d,sf[x].s*mu[d/sf[x].i]);}int cal(int n,int m){ int ans=0,r=0; if(n>m) swap(n,m); for(int i=1;i<=n;i=r+1){ r=min(n/(n/i),m/(m/i)); ans+=(sum(r)-sum(i-1))*(n/i)*(m/i); } return ans;}int ans[N];int main(int argc, const char * argv[]){ sieve(); sort(sf+1,sf+N);//!!!!! int T=read(); for(int i=1;i<=T;i++) q[i].n=read(),q[i].m=read(),q[i].a=read(),q[i].id=i; sort(q+1,q+1+T); int now=1; for(int i=1;i<=T;i++){ int a=q[i].a; for(;sf[now].s<=a;now++) ins(now); ans[q[i].id]=cal(q[i].n,q[i].m)&0x7FFFFFFF; } for(int i=1;i<=T;i++) printf("%d\n",ans[i]); return 0;}
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=1e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}struct ques{ int n,m,a,id; bool operator <(const ques &r)const{return a<r.a;}}q[N];int n,m;int notp[N],p[N],mu[N];struct data{ int s,i; bool operator <(const data &r)const{return s<r.s;}}sf[N];void sieve(){ mu[1]=1; for(int i=2;i<=100000;i++){ if(!notp[i]){ p[++p[0]]=i,mu[i]=-1; } for(int j=1,k;j<=p[0]&&(k=i*p[j])<=100000;j++){ notp[k]=1; if(i%p[j]==0){ mu[k]=0; break; } mu[k]=-mu[i]; } } for(int i=1;i<=100000;i++){ sf[i].i=i; for(int j=1;j*i<=100000;j++) sf[i*j].s+=i; }}int g[N];inline int lowbit(int x){return x&-x;}inline void add(int p,int v){for(int i=p;i<N;i+=lowbit(i)) g[i]+=v;}inline int sum(int p){ int ret=0; for(int i=p;i;i-=lowbit(i)) ret+=g[i]; return ret;}inline void ins(int x){ for(int d=sf[x].i;d<=100000;d+=sf[x].i) add(d,sf[x].s*mu[d/sf[x].i]);}int cal(int n,int m){ int ans=0,r=0; if(n>m) swap(n,m); for(int i=1;i<=n;i=r+1){ r=min(n/(n/i),m/(m/i)); ans+=(sum(r)-sum(i-1))*(n/i)*(m/i); } return ans;}int ans[N];int main(int argc, const char * argv[]){ sieve(); sort(sf+1,sf+100000); int T=read(); for(int i=1;i<=T;i++) q[i].n=read(),q[i].m=read(),q[i].a=read(),q[i].id=i; sort(q+1,q+1+T); int now=1; for(int i=1;i<=T;i++){ int a=q[i].a; for(;now<=100000&&sf[now].s<=a;now++) ins(now); ans[q[i].id]=cal(q[i].n,q[i].m)&0x7FFFFFFF; } for(int i=1;i<=T;i++) printf("%d\n",ans[i]); return 0;}
BZOJ 3529: [Sdoi2014]数表 [莫比乌斯反演 树状数组]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。