P1066 月的第十二章官方题解

Gioush OJ · 月的第十二章 · 2026/09/07 00:00

【部分分：测试点 1∼41\sim 41∼4】

当 $y\leq 10^3$ 时，我们可以把已经写完的行数 $x$ 看作状态。从 $x$ 出发，枚举 $1\leq k\leq \gcd(x,y)$ ，转移到状态 $x+k$ ，代价为 $1$ 。
从 $x=1$ 开始做最短路即可得到答案。所有转移始终令 $x$ 增大，所以也可以按照 $x$ 递增的顺序进行动态规划。对每个不同的 $y$ 记忆化答案后，不需要为重复数据重新计算。单次计算的时间复杂度为 $\mathcal{O}(y^2)$ ，空间复杂度为 $\mathcal{O}(y)$ 。

【部分分：测试点 5∼85\sim 85∼8】

特殊性质保证 $y$ 为质数。对于任意 $1\leq x<y$ ，都有 $\gcd(x,y)=1$ ，所以每个夜晚只能增加一行。
从 $1$ 增加到 $y$ 恰好需要 $y-1$ 个夜晚，单组数据可以在 $\mathcal{O}(1)$ 的时间内回答。这个性质提示我们：真正影响一次续写幅度的是 $y$ 的约数，而不需要保留所有中间位置。

【性质观察】

设当前已经到达 $x$ ，并令 $d=\gcd(x,y)$ 。若接下来始终增加 $d$ ，那么到达的每个中间位置仍然是 $d$ 的倍数，它与 $y$ 的最大公约数至少为 $d$ ，所以这些操作始终合法。
因此，从约数 $d$ 出发到达更大的约数 $e$ ，我们至多需要

\left\lceil\frac{e-d}{d}\right\rceil

个夜晚。若途中得到更大的最大公约数，就把它作为新的约数状态，继续进行同样的讨论。

【部分分：测试点 9∼129\sim 129∼12】

第一档的瓶颈是保留了 $1\sim y$ 的全部位置。根据上一页的观察，我们只保留 $y$ 的正约数。将它们从小到大写成 $d_1,d_2,\ldots,d_m$ ，其中 $d_1=1$ ， $d_m=y$ 。定义 $f_i$ 表示从 $1$ 到达 $d_i$ 所需的最少夜晚数，初值为 $f_1=0$ 。
枚举上一个约数状态，完整转移为

f_i=\min_{1\leq j<i} \left\{f_j+\left\lceil\frac{d_i-d_j}{d_j}\right\rceil\right\}.

答案为 $f_m$ ，不存在的状态视为正无穷。

【正解】

考虑一条最优续写过程。如果某一段过程在最大公约数为 $d$ 时没有到达新的约数状态，就可以把这一段调整为不断增加 $d$ ，直至抵达下一次出现的约数状态。这样不会增加夜晚数。于是总存在一条最优过程只需记录依次经过的约数。
枚举两个相邻的约数状态时，上页转移恰好计算了它们之间所需的最少夜晚数，因此动态规划既不会遗漏更优过程，也不会加入非法过程。
试除分解 $y$ 并递归生成全部约数。设 $\tau(y)$ 为约数个数，单组数据的时间复杂度为 $\mathcal{O}(\sqrt y+\tau(y)^2)$ ，空间复杂度为 $\mathcal{O}(\tau(y))$ 。相同的 $y$ 可以直接复用答案。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/184Name:moon_no_cht.cpp5You steal,I kill.6*/7#include <map>8#include <cstdio>9#include <vector>10#include <climits>11#include <algorithm>12#define MAXV 3163013using namespace std;14 15int c,T,y,Prime[4000],cnt=0;16bool Tag[MAXV];17map <int,int> Ans;18 19void Init(){20    for(int i=2;i<MAXV;i++){21        if(!Tag[i]) Prime[++cnt]=i;22        for(int j=1;j<=cnt&&i*Prime[j]<MAXV;j++){23            Tag[i*Prime[j]]=true;24            if(i%Prime[j]==0) break;25        }26    }27}28 29void Get_Div(int Now,long long Val,vector <pair<int,int> > &Fac,vector <int> &Div){30    if(Now==(int)Fac.size()){31        Div.push_back((int)Val);32        return;33    }34    for(int i=0;i<=Fac[Now].second;i++){35        Get_Div(Now+1,Val,Fac,Div);36        if(i<Fac[Now].second) Val*=Fac[Now].first;37    }38}39 40int Calc(int y){41    if(Ans.count(y)) return Ans[y];42    int Temp=y;43    vector <pair<int,int> > Fac;44    for(int i=1;i<=cnt&&1ll*Prime[i]*Prime[i]<=Temp;i++){45        if(Temp%Prime[i]) continue;46        int Count=0;47        while(Temp%Prime[i]==0){Temp/=Prime[i];Count++;}48        Fac.push_back(make_pair(Prime[i],Count));49    }50    if(Temp>1) Fac.push_back(make_pair(Temp,1));51 52    vector <int> Div;53    Get_Div(0,1,Fac,Div);54    sort(Div.begin(),Div.end());55 56    vector <int> Dp(Div.size(),0);57    for(int i=1;i<(int)Div.size();i++){58        int Best=INT_MAX;59        for(int j=i-1;j>=0;j--){60            int Step=(Div[i]-1)/Div[j];61            if(Step>=Best) break;62            Best=min(Best,Dp[j]+Step);63        }64        Dp[i]=Best;65    }66    return Ans[y]=Dp.back();67}68 69int main(){70    Init();71    scanf("%d%d",&c,&T);72    while(T-->0){73        scanf("%d",&y);74        printf("%d\n",Calc(y));75    }76    return 0;77}