【化学】实验 题解

· · 题解

自己的题，怎么能不写题解呢？

考察点：构图

我们可以新建n个点:n+1 \dots2n

第i个点表示i-n这个数

对于所有的a_i，将i与所有是a_i的约数的平方数的平方根所对应的节点号连一条边，权值为这个平方根

这样就可以转换成一个图论问题了！

也就是说，对于这张图，选出最大数量的点，使得两两之间不能由权值大于x的边相连。

我们很容易就可以发现， 在一个由权值大于x所组成的联通快中，最多只能选择一个。

所以跑n边dfs就可以了！

注意点1:

由于有2 \times 10^5个点和询问，所以裸的O(nm)是过不了的

通过打表可以发现，有很大一部分询问的答案是相同的

最多只需要查找\sqrt{max\{a_i\}}=200次即可。

所以只需要找到这个临界值就可以了

2.如何O(b_i^{\frac{1}{3}})求出c_i?

res=1;i=1
while i*i*i<=b[i]:
    cnt=0
    while b[i]%i==0:
        cnt=cnt+1
        b[i]=b[i]/i
    res=max(res,cnt)
last_b=b[i] 
tmp=sqrt(b[i])
if tmp*tmp==b[i]:res=max(res,2)
return res

为什么这段代码是正确的？

假设 last\_b=p*q

因为所有\le b_i^{\frac{1}{3}}的 因数都已经被while除完了

所以p,q一定为两个挺大的，互质的数

所以只要特判一下p,q是否相等即可

std:

#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int mxn=1000005;//real: 200000
int n,m;
int a[mxn],b[mxn],c[mxn];
vector<int>g[mxn];
int overban,t_o,mx;
bool use[mxn];
inline void dfs(int x){
    if(use[x])return;
    use[x]=1;
    if(x<=n)mx=max(mx,c[x]);
    for(int it=0;it<g[x].size();++it){
        int y=g[x][it];
        int ma=max(x,y);
        if(ma<=overban)continue;
        dfs(y);
    }
}
inline pair<int,int> solve(int xx){
    overban=xx;
    t_o=xx-n;
    int res=0,cnt=0;
    memset(use,0,sizeof(use));
    for(int i=1;i<=n;++i){
        if(!use[i]){
            mx=0;
            dfs(i);
            if(mx)++cnt;
            res+=mx;
        }
    }
    return mp(cnt,res);
}
pair<int,int>ans[mxn];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
        for(int x=2;x*x<=a[i];++x){
            if(a[i]%(x*x)==0){
                g[i].push_back(n+x);
                g[n+x].push_back(i);
            }
        }
    }
    for(int i=1;i<=n;++i){   //b[i]^(1/3) calc c[i]
        scanf("%d",b+i);
        int t=b[i],res=1;
        for(int x=2;x*x*x<=t;++x){
            int c=0;
            for(;t%x==0;t/=x)++c;
            res=max(res,c);
        }
        int t2=sqrt(t);
        if(t2*t2==t)res=max(res,2);
        else res=max(res,1);
        c[i]=res;
    }
    for(int i=1;i<=200000;++i){
        if(ans[i-1].first==n){
            ans[i]=ans[i-1];
            continue;
        }
        ans[i]=solve(i+n);
    }
    for(int i=1;i<=m;++i){
        int x;scanf("%d",&x);
        printf("%d %d\n",ans[x].first,ans[x].second);
    }
    return 0;
}