[罪人的终幕] 题解

· · 题解

感谢 @PengAo 对这篇题解的建议和修改。

题目大意

定义 \operatorname{a}(n)=\sum_{p|n}p，若 m_i=\max_{j<i}\left\lbrace\frac{m_j}{\operatorname{a}(\operatorname{lcm}(w_i,w_j))+\operatorname{a}(\gcd(w_i,w_j))} \right\rbrace+k，求 \sum m_i。

题解

下文以求方便，用 f_i 表示 m_i：

\begin{aligned} f_i&=\max_{j<i}\left\lbrace\frac{f_j}{\operatorname{a}(\operatorname{lcm}(w_i,w_j))+\operatorname{a}(\gcd(w_i,w_j))}\right\rbrace+k\\ &=\min_{j<i}\left\lbrace\frac{\operatorname{a}(\operatorname{lcm}(w_i,w_j))+\operatorname{a}(\gcd(w_i,w_j))}{f_j}\right\rbrace^{-1}+k\\ &=\min_{j<i}\left\lbrace\frac{\operatorname{a}(w_iw_j)+\operatorname{a}(\gcd(w_i,w_j))}{f_j}\right\rbrace^{-1}+k\\ &=\min_{j<i}\left\lbrace\frac{\operatorname{a}(w_i)+\operatorname{a}(w_j)}{f_j}\right\rbrace^{-1}+k\\ &=\min_{j<i}\left\lbrace\frac{\operatorname{a}(w_i)}{f_j}+\frac{\operatorname{a}(w_j)}{f_j}\right\rbrace^{-1}+k\\ \end{aligned}

注意到 \min 里面可以用李超线段树维护，并且可以线性筛求出 \operatorname{a}(n)，从而 O(n\log n) 解决。

关于变形的证明（以下的 p_i 均为质数）：

i=\prod_{p_k|i} p_k^{c_k},i'=\prod_{p_k|i} p_k,\\ \operatorname{a}(i)=\sum_{p_k|i} p_k,\operatorname{a}(i')=\sum_{p_k|i} p_k\Rightarrow \operatorname{a}(i)=\operatorname{a}(i')

同理，\operatorname{a}(j)=\operatorname{a}(j')，设 g'=\gcd(i',j'),g=\gcd(i,j)，易得 \gcd(g',\frac{i'}{g'})=1,\gcd(j',\frac{i'}{g'})=1：

\begin{aligned} \operatorname{a}(i)+\operatorname{a}(j)&=\operatorname{a}(i')+\operatorname{a}(j')\\ &=\operatorname{a}(\frac{i'}{g'})+\operatorname{a}(j')+\operatorname{a}(g')\\ &=\operatorname{a}(i'j')+\operatorname{a}(g')\\ &=\operatorname{a}(\operatorname{lcm}(i,j))+\operatorname{a}(\gcd(i,j)) \end{aligned}

证毕。

代码如下：

#include<bits/stdc++.h>
#define N 200010
#define I_love_Furina return
#define forever 0
#define foreverr 1
#define Endl endl
#define endl '\n'
#define FIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define db long double
#define chc cout<<114514<<endl
#define int long long
#define lt (p<<1)
#define rt (p<<1|1)
#define mid (l+r>>1)
#define eps 1e-15
#define ma 1e9
#define day 182376
using namespace std;
int n,T,pr[N],num,w[N],t[N<<2];
db k,dp[N],d[N];
bool b[N];
struct line{db k,b;}li[N];
inline int cmp(db x,db y){
    if(fabs(x-y)<eps)I_love_Furina forever;
    I_love_Furina (x>y?1:-1);
}
inline void mk(int p){li[++num].k=1.0/dp[p],li[num].b=d[w[p]]/dp[p];}
inline db calc(int p,int x){I_love_Furina li[p].k*x+li[p].b;}
inline void upd(int p,int l,int r,int u){
    int &v=t[p],tp=cmp(calc(u,mid),calc(v,mid));
    if(tp<0)swap(u,v);
    int tpl=cmp(calc(u,l),calc(v,l)),tpr=cmp(calc(u,r),calc(v,r));
    if(tpl<0)upd(lt,l,mid,u);
    if(tpr<0)upd(rt,mid+1,r,u);
}
inline db query(int p,int l,int r,int x){
    if(l>x||r<x)I_love_Furina ma;
    db ans=calc(t[p],x);
    if(l==r)I_love_Furina ans;
    I_love_Furina min(ans,min(query(lt,l,mid,x),query(rt,mid+1,r,x)));
}
signed main(){
    IOS;//FIO("");
    n=2e5;
    d[1]=0;
    for(int i=2;i<=n;i++){
        if(!b[i])pr[++num]=i,d[i]=i;
        for(int j=1;j<=num&&i*pr[j]<=n;j++){
            b[i*pr[j]]=1;
            if(i%pr[j]==0){d[i*pr[j]]=d[i];break;}
            d[i*pr[j]]=d[i]+d[pr[j]];
        }
    }
    num=0;
    li[0].k=1145,li[0].b=100000000;
    cin>>n>>dp[1]>>k;
    for(int i=1;i<=n;i++)cin>>w[i];
    mk(1);
    //cout<<num<<" "<<li[1].k<<" "<<li[1].b<<endl;
    upd(1,1,day,1);
    for(int i=2;i<=n;i++)dp[i]=1/query(1,1,day,d[w[i]])+k,mk(i),upd(1,1,day,i);
    db sum=0;
    for(int i=1;i<=n;i++)sum+=dp[i];
    printf("%.6Lf",sum);
    I_love_Furina forever;
}

P.S. 本来出这道题不容易，还要求我给证明 qnq。