CF1978F Sol

CarroT1212 · 2024-06-17 19:58:44 · 题解

被 C&D 创了没细想，哈哈。

感觉像是考验注意力的题目，于是你尝试注意一些东西。然后注意到 k\ge 2？

说明斜着相邻的格子如果有 \gcd>1 必定连边。那题目里有什么格子是斜着相邻的呢？

很明显有每个 a_i 在循环移位之后分成的至多两条全是 a_i 的斜线。除了 a_i=1，特判掉即可。

比如题面里这个矩阵。3 是完整的一条，4,5 都被分成两条。

所以每条这样的斜线（除了 a_i=1）必定形成一个连通块。而相邻两条斜线的距离是 1，于是我们把二维问题完全的转为了一维。把斜线上的数分别写下来得到 4\ 5\ 3\ 4\ 5。在这个上面再去做。令它为新的 a_i。

那这就比较好做了。预处理每个数的质因子，每次求一下每个质因子被哪些 a_i 包含。对于包含同一个质因子的 a_i，我们将距离不超过 k 的相邻两个数连在一起。对每一个存在 a_i 包含的质因子这么做一遍。并查集维护一下，得到最终的连通块数量就完事了。

注意由于多测的存在，枚举包含的质因子的时候必须只枚举存在至少一个 a_i 包含的，然后枚举包含质因子的数的时候也得预处理出来，不能多枚。

复杂度是 O(n\ln n) 左右的东西。

记得特判 a_i=1。

ll n,k,a[N*2],vis[N],ans;
vector<ll> prm[N],cnt[N],has;
struct dsu {
    ll f[N*2];
    void ini(ll n) { iota(f+1,f+n+1,1); }
    void mrg(ll x,ll y) { f[fnd(x)]=fnd(y); }
    ll fnd(ll x) { return f[x]==x?x:f[x]=fnd(f[x]); }
} D;
void mian() {
    for (ll i=2;i<N;i++) if (!vis[i]) {
        prm[i].pb(i);
        for (ll j=i+i;j<N;j+=i) vis[j]=i,prm[j].pb(i); 
    }
    scanf("%lld%lld",&n,&k),ans=0;
    for (ll i=1;i<=n;i++) {
        scanf("%lld",&a[i+n-1]);
        if (a[i+n-1]==1) ans+=n;
    }
    for (ll i=1;i<n;i++) a[i]=a[i+n];
    has.clear();
    for (ll i=1;i<n*2;i++) for (ll j:prm[a[i]]) has.pb(j),cnt[j].pb(i);
    sort(has.begin(),has.end());
    ll len=unique(has.begin(),has.end())-has.begin();
    D.ini(n*2-1);
    for (ll i=0;i<len;i++) {
        for (ll j=0;j+1<cnt[has[i]].size();j++)
            if (cnt[has[i]][j+1]-cnt[has[i]][j]<=k) D.mrg(cnt[has[i]][j+1],cnt[has[i]][j]);
        cnt[has[i]].clear();
    }
    set<ll> s;
    for (ll i=1;i<n*2;i++) if (a[i]>1) s.insert(D.fnd(i));
    cout<<ans+s.size()<<"\n";
}