P8155 「PMOI-5」公约数变换

· · 题解

传送门

在开始前我们先思考一个简化版：

我们将 $a_1$ 拆成 $\gcd(a_1,m)\times x$，然后一次操作就相当于将 $a_1$ 变成 $\gcd(a_1,m)\times (x+1)$。 但是 $x$ 会就这样一直加下去吗？显然不是的。当 $\gcd(\frac{m}{\gcd(a_1,m)},x)>1$ 时，$\gcd(a_1,m)$ 会乘 $y$，$x$ 会除以 $y$。 但是上述操作只会进行大约 $\log m$ 次。因为 $\gcd(a_1,m)<=m$，所以不可能做超过 $\log m$ 次乘法。 因此我们可以尝试求出每次操作相比上一次 $x$ 加了多少，就能求出最终变换次数。 怎么求呢？ 我们先求出所有当前 $\frac{m}{\gcd(a_1,m)}$ 的质因子的倍数中 $≥x$ 且值最小的数，这就是我们下一次操作时 $x$ 的值。然后更新 $\gcd(a_1,m)$ 和 $x$ 到下一次操作后的值。 就这样做大约 $\log m$ 次，直到 $\gcd(a_1,m)=m$ 就可以求出答案。 然后扩展到原题。 首先需要知道 $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$。 对于 $a_i$，我们发现前面的 $\gcd(a_1,a2,...,a_{i-1})$ 只有大约 $\log m$ 种可能。 为什么？ 先证明每次从前面过来的 $\gcd$ 都是上一次的倍数。 我们考虑递推证明。 假设 $\gcd(m,a_1,a2,...,a_{i-1})$ 满足上述情况。若 $a_i$ 不变则很简单。现在有 $x$ 的影响。但是 $x$ 的质因子只要被乘进 $\gcd$ 里面就不会再出来了。所以 $\gcd(m,a_1,a2,...,a_i)$ 满足上述情况。 同时 $\gcd(m)$ 满足上述情况，顺着推下去即可。证毕。 然后很简单的结论：**每次 $\gcd$ 改变都会乘一个数**。最多乘 $\log m$ 次，所以只会有 $\log m$ 种可能。 于是对于前面过来的每个 $\gcd$，我们都按照 $n=1$ 操作一遍，只不过多了个变换次数上限。然后就可以求出每个位置的 $a_i$ 需要变换几次才能符合要求。取 $\max$ 即可。 因为分解质因数是 $O(\sqrt{m})$ 的，所以作者先分解然后直接用质因数做。复杂度多了一个 $\log$。 复杂度 $O(\sqrt{m}+n\log^2m)

其实复杂度是不到的。因为里面大多数的数都没有 \log m 个质因数。

代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define N 100010
using namespace std;

ull n,m,a[N],f[2][65][65],t[2][65],cnt[2],c[2][65],ans;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%llu",&a[i]);
    ull x=2;
    while(m>1)
    {
        if(m%x==0) 
            m/=x,f[0][1][++c[0][1]]=x,x=1;
        x++;if(x*x>m) break;
    }
    if(m!=1) f[0][1][++c[0][1]]=m;
    t[0][2]=8e18;cnt[0]=1;
    ull now,cur;bool u;
    for(int i=1;i<=n;i++)
    {
        u^=1;cur=a[i];cnt[u]=0;now=0;
        memset(f[u],0,sizeof(f[u]));
        memset(c[u],0,sizeof(c[u]));
        for(int j=1;j<=cnt[u^1];j++)
        {
            cur+=(t[u^1][j]-now);now=t[u^1][j];
            ull p=t[u^1][j+1],w[60];int c1,nd;
            while(true)
            {
                c1=1;nd=0;
                for(int k=1;k<=c[u^1][j];k++)
                    if(f[u^1][j][k]!=f[u][cnt[u]][c1])
                        w[++nd]=f[u^1][j][k];
                    else c1++;
                ull mi=8e18,q=-1;
                for(int k=1;k<=nd;k++)
                    if(((cur-1)/w[k]+1)*w[k]-cur<=p-now)
                        if(((cur-1)/w[k]+1)*w[k]-cur<mi)
                            mi=((cur-1)/w[k]+1)*w[k]-cur,q=w[k];
                if(q==-1) break;
                now+=((cur-1)/q+1)*q-cur;cur=(cur-1)/q+1;
                cnt[u]++;
                for(int k=1;k<=c[u][cnt[u]-1];k++)
                    f[u][cnt[u]][k]=f[u][cnt[u]-1][k];
                c[u][cnt[u]]=c[u][cnt[u]-1];
                f[u][cnt[u]][++c[u][cnt[u]]]=q;
                int s=c[u][cnt[u]];
                while(s>1&&f[u][cnt[u]][s]<f[u][cnt[u]][s-1])
                    swap(f[u][cnt[u]][s],f[u][cnt[u]][s-1]),s--;
                t[u][cnt[u]]=now;
            }
        }
        ans=max(ans,now);t[u][cnt[u]+1]=8e18;
    }
    cout<<ans<<endl;
    return 0;
}