自动搬运

查看原文

来自洛谷，原作者为

	Furina 芙宁娜太可爱啦！| 青雀太可爱啦！ | 题单 592617

搬运于2025-08-24 23:03:29，当前版本为作者最后更新于2024-07-29 15:17:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

感谢

题解的建议和修改。

题目大意

定义 $\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。