对于 30% 的数据, 满足 N 1000, R ? L 1000;
对于另外的 30% 的数据, 满足 N 10^5, L = R;
对于 100% 的数据, 满足 N 10^5, Di 10^5, 1 L R 10^5.
注意: 版权归杨乐所属!!
清北寒假省选班的最后一次考试的压轴题, 当时我远程提交 (厚颜无耻) 了个暴力竟然得了 80 分!!! 震惊!
我的暴力就是维护一个点到子树中的每种 gcd 路径的数量, 然后合并, 计算答案
所以先贴一个我的暴力 (沉迷重载运算符无法自拔)
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cstdlib>
- #include<cmath>
- #include<vector>
- #define ll long long
- #define maxn 150005
- #define pb push_back
- using namespace std;
- ll ans=0,base=0;
- int to[maxn*2],ne[maxn*2],val[maxn*2];
- int hd[maxn],u,v,n,m,L,R;
- int vis[maxn],dfn,pos[maxn];
- int gcd(int a,int b){
- return b?gcd(b,a%b):a;
- }
- struct p{
- int num,sum;
- };
- struct node{
- vector<p> g;
- node operator *(const int &u)const{
- node r; p x;
- r.g.clear();
- dfn++;
- for(int i=g.size()-1;i>=0;i--){
- x=g[i];
- int d=gcd(u,x.num);
- if(vis[d]!=dfn){
- vis[d]=dfn,pos[d]=r.g.size();
- r.g.pb((p){d,x.sum});
- }
- else{
- r.g[pos[d]].sum+=x.sum;
- }
- }
- return r;
- }
- node operator +(const node &u){
- node r; p x;
- r.g.clear();
- dfn++;
- for(int i=g.size()-1;i>=0;i--){
- x=g[i];
- if(vis[x.num]!=dfn){
- vis[x.num]=dfn,pos[x.num]=r.g.size();
- r.g.pb(x);
- }
- else r.g[pos[x.num]].sum+=x.sum;
- }
- for(int i=u.g.size()-1;i>=0;i--){
- x=u.g[i];
- if(vis[x.num]!=dfn){
- vis[x.num]=dfn,pos[x.num]=r.g.size();
- r.g.pb(x);
- }
- else r.g[pos[x.num]].sum+=x.sum;
- }
- return r;
- }
- }tree[maxn];
- inline ll calc(node x,node y){
- ll an=0;
- p o,k;
- for(int i=x.g.size()-1;i>=0;i--){
- o=x.g[i];
- for(int j=y.g.size()-1;j>=0;j--){
- k=y.g[j];
- if(gcd(k.num,o.num)==1) an+=k.sum*(ll)o.sum;
- }
- }
- return an;
- }
- inline ll calc_line(node x,node y,int D){
- ll an=0;
- p o,k;
- for(int i=x.g.size()-1;i>=0;i--){
- o=x.g[i];
- for(int j=y.g.size()-1;j>=0;j--){
- k=y.g[j];
- if(gcd(gcd(k.num,o.num),D)==1) an+=k.sum*(ll)o.sum;
- }
- }
- return an;
- }
- void dfs(int x,int fa){
- tree[x].g.pb((p){0,1});
- node w;
- for(int i=hd[x];i;i=ne[i]) if(to[i]!=fa){
- dfs(to[i],x);
- w=tree[to[i]]*val[i];
- ans+=calc(tree[x],w);
- tree[x]=tree[x]+w;
- }
- }
- int main(){
- freopen("touch.in","r",stdin);
- freopen("touch.out","w",stdout);
- scanf("%d%d%d",&n,&L,&R);
- scanf("%d%d",&u,&v);
- int uu,vv,ww;
- for(int i=n-2;i;i--){
- scanf("%d%d%d",&uu,&vv,&ww);
- to[i]=vv,ne[i]=hd[uu],hd[uu]=i,val[i]=ww;
- i+=n;
- to[i]=uu,ne[i]=hd[vv],hd[vv]=i,val[i]=ww;
- i-=n;
- }
- dfs(u,u),dfs(v,v);
- for(int i=L;i<=R;i++) printf("%lld\n",ans+calc_line(tree[u],tree[v],i));
- return 0;
- }
然后来正经的讲一下正解咳咳
(要不是当时 T2 是我第一次写高精调了大半年最后没时间了我觉得我是能想到的 hhh)
设 f[x]为路径 gcd 为 x 的点对对数, g[x]为路径 gcd 为 x 的倍数的点对对数
显然 g[x]=Σf[x*i]
那么反演一下, f[x]=Σg[x*i]*μ[i]
然后我们求的是 f[1], 所以答案就是Σg[i]*μ[i] (先假装没有那条边权不定的边)
求 g[x]很简单, 并查集一下就好了
那么怎么考虑那条边权不确定的边呢???
设那条不确定的边的边权是 w
它只会对 d|w 的 g[d]产生影响, 而且影响也是很好计算的, 就在计算 g[d]之后的并查集上再连一下不定边的两个端点即可
至于计算所有 g[d]和考虑所有 d 对 d|w 的 w 的影响的话, 可以用调和级数开开心心 O(N log N)过的 (我是不会告诉你标程是 N sqrt(N) 然后我艹爆了标程 hhh,
其实是老师懒懒得写调和级数)
这样的话其实时限 1s 就够了(当然如果时限 1s 我当时就没法水那么多暴力分了 hhh)
- #include<iostream>
- #include<cmath>
- #include<algorithm>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<vector>
- #define ll long long
- #define maxn 100005
- #define pb push_back
- using namespace std;
- vector<int> g[maxn];
- int zs[maxn],t=0,miu[maxn];
- bool v[maxn];
- inline void init(){
- miu[1]=1;
- for(int i=2;i<=100000;i++){
- if(!v[i]) zs[++t]=i,miu[i]=-1;
- for(int j=1,u;j<=t&&(u=zs[j]*i)<=100000;j++){
- v[u]=1;
- if(!(i%zs[j])) break;
- miu[u]=-miu[i];
- }
- }
- }
- int num,op[maxn],mx;
- int vis[maxn],dfn=0;
- struct lines{
- int u,v;
- }l[maxn];
- int n,m,S,T,L,R;
- int p[maxn],siz[maxn];
- ll base=0,ans[maxn];
- int ff(int x){
- return p[x]==x?x:(p[x]=ff(p[x]));
- }
- inline void clear(){
- for(int i=1;i<=num;i++){
- p[op[i]]=op[i];
- siz[op[i]]=1;
- }
- p[S]=S,p[T]=T;
- siz[S]=siz[T]=1;
- num=0;
- }
- inline ll solve(int x){
- dfn++;
- lines e;
- int fa,fb;
- ll an=0;
- for(int i=x;i<=mx;i+=x)
- for(int j=g[i].size()-1;j>=0;j--){
- e=l[g[i][j]];
- fa=ff(e.u),fb=ff(e.v);
- if(vis[e.u]!=dfn){
- vis[e.u]=dfn,op[++num]=e.u;
- }
- if(vis[e.v]!=dfn){
- vis[e.v]=dfn,op[++num]=e.v;
- }
- p[fa]=fb,an+=siz[fa]*(ll)siz[fb];
- siz[fb]+=siz[fa];
- }
- return an;
- }
- int main(){
- init();
- scanf("%d%d%d",&n,&L,&R);
- scanf("%d%d",&S,&T);
- int ww;
- for(int i=n-2;i;i--){
- scanf("%d%d%d",&l[i].u,&l[i].v,&ww);
- g[ww].pb(i),mx=max(mx,ww);
- }
- for(int i=1;i<=n;i++) p[i]=i,siz[i]=1;
- for(int i=mx;i;i--){
- clear();
- base+=miu[i]*solve(i);
- int fa=ff(S),fb=ff(T);
- ll now=siz[fa]*(ll)siz[fb]*(ll)miu[i];
- for(int j=i;j<=mx;j+=i) ans[j]+=now;
- }
- for(int i=L;i<=R;i++) printf("%lld\n",base+ans[i]);
- return 0;
- }
但是暴力还是在 loj 上 A 了, 对比一下(根据数据的随机性的话, 我这种暴力的效果也是很好的):
来源: http://www.bubuko.com/infodetail-2497177.html