Steps to One 题解_牛客博客

挺简单的一道概率dp+简单数论+简单容斥题目。

~~由于是编译器小白，枚举了n次编译器qwq。。。~~

c++的同学建议用clang++17那个编译器qwq

一.概率dp+简单数论部分

比较容易想到的，我们设 $dp[i]$ 表示当前gcd为i，期望 $dp[i]$ 步后到达1

初始化 $dp[1]=0$

然后，我们来推下转移方程:

$dp[i]=\frac{\sum_{j=1}^ndp[gcd(i,j)]}{n}+1(转移走一步)$

明显的有， $gcd(i,j)<=i$

那么，我们只要分 $gcd(i,j)=i,和gcd(i,j)\not =i$ 两种情况分开讨论即可。

注意到， $gcd(i,j)=i$ 当且仅当 $i|j$ ,也即是共有 $[\frac{n}{i}]$ 个 $dp[i]$

当 $gcd(i,j)\not =i$ 时，即 $i\not|j$ 我们设 $al=\sum_{i\not|j,j\in[1,n]}dp[gcd(i,j)],tot=[\frac{n}{i}]$

那么将原转移方程移项后有:

$\frac{n-tot}{n}dp[i]=\frac{al}{n}+1$

$dp[i]=\frac{n+al}{n-tot}$

因为n和al的值都可以O(1)获得，那么，我们只需要计算出al就好了。

我们直接枚举j肯定不行的，会T惨，那么，我们考虑枚举 $gcd(i,j)$

因为，有 $gcd(i,j)$ 一定是i的约数，所以我们 $O(\sqrt{n})$ 枚举i的所有约数即可

设当前枚举的 $gcd$ 为k

那么，我们现在需要计算的就是，究竟有多少个 $j\in[1,n]$ 使得 $gcd(i,j)=k$

那么，我们用式子表达出来就是 $\sum_{j=1}^{n}[gcd(i,j)==k]$

这就等价于求 $\sum_{j=1}^{[\frac{n}{k}]}[gcd(\frac{i}{k},j)==1]$

即是求 $[1,[\frac{n}{k}]]$ 中，与 $\frac{i}{k}$ 互质的数的个数

二.简单数论+简单容斥部分

为了好看，我们设 $C=\frac{n}{k},x=\frac{i}{k}$

那么，我们现在就需要求出 $[1,C]$ 中与x互质的数的个数。

这个怎么做呢？

我们把x分解质因数： $x=p_1^{a_1}...p_k^{a_k}(a_i\in N^*)$

那么，一个数要与x互质，必须不是 $p_1,p_2...p_k$ 的倍数，那么我们只需减去C中 $p_1或p_2...或p_k$ 的倍数的数字即可。直接容斥就好了！

那么复杂度呢？直接容斥不会超时吗？

我们分析下，因为单次求，复杂度只和质数的个数有关，所以，我们直接选最小的几个质数就行了。

因为有: $2*3*5*7*11*13*17$ =510510<100000

所以，一个数最多只能分出6个不同的质数出来，所以单词容斥的上限是 $2^6=64$ ,而这明显是跑不满的，所以不会超时。

于是，到此，我们求出了所有的dp值了，那么答案怎么求呢？

很简单，我们枚举我们第一个放进去的数即可，那么，答案就是:

$Ans=\frac{\sum_{i=1}^{n}dp[i]}{n}+1$

于是此题解完。（除的部分记得用逆元乘法代替）

代码:

#include<stdio.h>
#include<cmath>
using namespace std;
const int mod=1e9+7,N=1e5+1;
int dp[N],n,g[N],f[N],e,tim;
int vis[N],sav[N],ep,ans,m;
inline void sai(){//为了分解质因数，处理出一个数的任意质因数函数g
    for(int i=2;i<N;++i){
        if(!g[i]){
            f[++e]=i;g[i]=i;
        }
        for(int j=1;j<=e;++j){
            if(i*f[j]>=N)break;
            g[i*f[j]]=f[j];
            if(i%f[j]==0)break;
        }
    }
}
inline void dfs(int now,int s,int num){//容斥
    if(now==ep+1){
        if(num){
            if(num&1){
                ans-=(m/s);
            }else{
                ans+=(m/s);
            }
        }
        return;
    }
    dfs(now+1,s,num);
    dfs(now+1,s*sav[now],num+1);
}
inline int calc(int x,int y){//计算1-n中与x的gcd为y的数的个数
    ++tim;ep=0;
    x/=y;m=n/y;ans=m;
    while(g[x]){
        if(vis[g[x]]!=tim)sav[++ep]=g[x],vis[g[x]]=tim;
        x/=g[x];
    }
    dfs(1,1,0);
    return ans;
}
inline int ksm(int x,int y){
    int ans=1;
    while(y){
        if(y&1)ans=(1LL*ans*x)%mod;
        x=(1LL*x*x)%mod;y>>=1;
    }
    return ans;
}
int main(){
    sai();
    dp[1]=0;
    scanf("%d",&n);
    for(int i=2;i<=n;++i){
        int tot=n/i,al=0;
        for(int j=sqrt(i);j;--j){//枚举gcd
            if(i%j==0){
                (al+=(1LL*dp[j]*calc(i,j))%mod)%=mod;
                if(i!=1&&i/j!=j){
                    (al+=(1LL*dp[i/j]*calc(i,i/j))%mod)%=mod;
                }
            }
        }
        dp[i]=(1LL*(n+al)*ksm(n-tot,mod-2))%mod;
    }
    ans=0;
    for(int i=1;i<=n;++i){
        ans=(ans+dp[i])%mod;
    }
    ans=(1LL*ans*ksm(n,mod-2)+1)%mod;
    printf("%d",ans);
    return 0;
}