首页 > 代码库 > BZOJ3853: GCD Array
BZOJ3853: GCD Array
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3853
题解：我们发现直接修改是肯定不行的。因为一次有可能修改的很多。而且编号也是不连续的。
搬运题解：
{
注意到给所有gcd(x,n)==d的数加上v等价于给每个数加上[gcd(x,n)==d]*v，而我们可以发现：
[gcd(x,n)==d]*v =>
[gcd(x/d,n/d)==1] *v=>
sigma(mu[q] * v) (q | n/d && q | x/d)
=> sigma(mu[q] * v) (q | n/d && q*d | x)
其中mu是莫比乌斯函数
我们可以构造一个数组f，让a[i] == sigma(f[j]) (j | i)，然后修改操作就变成了：对所有满足条件的q，让f[q*d]加上mu[q] * v，那么根据f数组的性质，我们每个a[i]就能很顺利的加上[gcd(x,n)==d]*v了。
}
其实这相当与我们把修改和查询都往前推了一下，推到了一个公共的部分，然后发现这个部分维护所需时间在允许范围内。so。。。
这题的思想还需要领悟。。。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 200000 26 27 #define maxm 200000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go) 44 45 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) 46 47 #define mod 1000000007 48 49 using namespace std; 50 51 inline int read() 52 53 { 54 55 int x=0,f=1;char ch=getchar(); 56 57 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 58 59 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 60 61 return x*f; 62 63 } 64 int n,m,mu[maxn+1],p[maxn],tot; 65 ll s[maxn]; 66 bool v[maxn+1]; 67 vector<int>fac[maxn+1]; 68 inline void add(int x,int y) 69 { 70 for(;x<=n;x+=x&(-x))s[x]+=y; 71 } 72 inline ll sum(int x) 73 { 74 ll t=0; 75 for(;x;x-=x&(-x))t+=s[x]; 76 return t; 77 } 78 inline void get() 79 { 80 mu[1]=1; 81 for2(i,2,maxn) 82 { 83 if(!v[i])p[++tot]=i,mu[i]=-1; 84 for1(j,tot) 85 { 86 int k=i*p[j]; 87 if(k>maxn)break; 88 v[k]=1; 89 if(i%p[j])mu[k]=-mu[i]; 90 else {mu[k]=0;break;} 91 } 92 //cout<<i<<‘ ‘<<mu[i]<<endl; 93 } 94 for1(i,maxn) 95 for(int j=i;j<=maxn;j+=i) 96 fac[j].push_back(i); 97 } 98 99 int main()100 101 {102 103 freopen("input.txt","r",stdin);104 105 freopen("output.txt","w",stdout);106 get();107 108 for1(cs,inf)109 {110 n=read();m=read();111 if(!n&&!m)break;112 printf("Case #%d:\n",cs);113 memset(s,0,sizeof(s));114 while(m--)115 {116 int op=read();117 if(op==1)118 {119 int x=read(),y=read(),z=read();120 if(x%y)continue;121 x/=y;122 for3(i,fac[x].size()-1,0)add(fac[x][i]*y,mu[fac[x][i]]*z);123 }else124 {125 int t=read();ll ans=0;126 for(int i=1,j;i<=t;i=j+1)127 {128 j=t/(t/i);129 ans+=(ll)t/i*(sum(j)-sum(i-1));130 }131 printf("%lld\n",ans);132 }133 }134 }135 136 return 0;137 138 }
BZOJ3853: GCD Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。