题目概述

CF1139D

解题报告

这是2021天梯赛L3-3的弱化版，吉老师加强版又要杜教筛又要快速乘，懒得写了XD。

直接推式子（ $1\over n$ 是长度为 $1$ 的情况，需要单独处理）：

$$ \begin{aligned} ans&={1\over n}+\sum_{L=2}^{+\infty}{(\sum{[(a_1,a_2,\cdots,a_n)=1])-n(\sum[(a_1,a_2,\cdots,a_{n-1})=1]})\over n^L}L\\ &={1\over n}+\sum_{L=2}^{+\infty}{L\over n^L}[\sum_{d|(a_1,a_2,\cdots,a_n)}\mu(d)-n\sum_{d|(a_1,a_2,\cdots,a_{n-1})}\mu(d)]\\ &={1\over n}+\sum_{L=2}^{+\infty}{L\over n^L}\sum_{d=1}^{n}\mu(d)(\lfloor{n\over d}\rfloor^L-n\lfloor{n\over d}\rfloor^{L-1})\\ \end{aligned} $$

令 $x=\lfloor{n\over d}\rfloor$ ，$q={x\over n}$ ，则：

$$ \begin{aligned} ans&={1\over n}+\sum_{L=2}^{+\infty}\sum_{d=2}^{n}\mu(d){L\over n^L}(x^L-nx^{L-1})\\ &={1\over n}+\sum_{L=2}^{+\infty}\sum_{d=2}^{n}\mu(d)L(q^L-q^{L-1})\\ &={1\over n}+\sum_{d=2}^{n}\mu(d)\sum_{L=2}^{+\infty}L(q^L-q^{L-1})\\ &={1\over n}+\sum_{d=2}^{n}\mu(d)(-2q-{q^2\over 1-q})\\ \end{aligned} $$

所以就可以 $O(n\log_2MOD)$ 得出答案了。

不过我们不难发现 $x$ 是可以除法分块的，所以可以利用除法分块+杜教筛求 $\mu(n)$ 前缀和优化。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000,MOD=1e9+7;

int n,ans,p[maxn+5],u[maxn+5];bool pri[maxn+5];

void Make(int n){
    u[1]=1;
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i,u[i]=-1;
        for (int j=1,t;j<=p[0] && (t=i*p[j])<=n;j++)
            {pri[t]=true;u[t]=-u[i];if (!(i%p[j])) {u[t]=0;break;}}
    }
    for (int i=1;i<=n;i++) u[i]=(u[i]+MOD)%MOD;
}
#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=MUL(s,w);b>>=1;w=MUL(w,w);}return s;}
int main(){
    scanf("%d",&n);Make(n);
    int INV=Pow(n,MOD-2);ans=INV;
    for (int i=2;i<=n;i++){
        int x=n/i,q=MUL(x,INV);
        int A=MUL(MUL(q,q),Pow(MOD+1-q,MOD-2));
        A=ADD(A,(q<<1)%MOD);
        ans=ADD(ans,MUL(MOD-A,u[i]));
    }
    printf("%d\n",(ans+MOD)%MOD);
    return 0;
}