30分求调
查看原帖
30分求调
511268
PIKA_PIKA楼主2024/8/31 09:36
#include<bits/stdc++.h>
#define int long long
#define db double
using namespace std;
const int N=1e6+10,mod=998244353;
const long double eps=1e-9,mx=1e9;
int n,w[N],p[N],tt,num,s[N<<2],df[N];
db m[N],ans,k;
bool v[N];
struct Ed{
    db k,b;
}li[N];
inline void mk(int p){li[++num].k=1.0/m[p],li[num].b=(double)df[w[p]]/m[p];}
#define Y(i,x) (li[i].b+li[i].k*x)
void init(int n)
{
    for (int i = 2; i <= n; i ++ ){
        if (!v[i]) p[tt ++ ] = i, df[i] = i;
        for (int j = 0; p[j] * i <= n; j ++ ){
            v[i*p[j]] = true;
            if (i % p[j] == 0) {df[i*p[j]]=df[i];break;}
            df[i*p[j]]=df[i]+p[j];
        }
    }
}
void modify(int k,int l,int r,int p){
    int mid=(l+r)>>1;
    if(Y(p,mid)<Y(s[k],mid)) swap(s[k],p);
	if(l==r)return;
	if(Y(p,l)<Y(s[k],l)) modify(k<<1,l,mid,p);
	if(Y(p,r)<Y(s[k],r)) modify(k<<1|1,mid+1,r,p);
}
db query(int k,int l,int r,int p){
    if(l==r) return Y(s[k],l);
    int mid=l+r>>1; db val=Y(s[k],p);
    if(p<=mid) val=min(val,query(k<<1,l,mid,p));
    else val=min(val,query(k<<1|1,mid+1,r,p));
    return val;
}
signed main(){
    init(N-1);
    scanf("%d%lf%lf",&n,&m[1],&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }li[0].k=1000000,li[0].b=100000000;
    mk(1);modify(1,1,n,1);
    for(int i=2;i<=n;i++){
        m[i]=1/query(1,1,n,df[w[i]])+k;mk(i);
        modify(1,1,n,i);
    }
    for(int i=1;i<=n;i++)ans+=m[i];
    printf("%.10lf",ans);
}
2024/8/31 09:36
加载中...