2020牛客暑期多校训练营（第一场）B. Infinite Tree

题解

可以认为u是，同时是递减的，即为从根1走到后再走到，那么考虑枚举质数和每种质数的个数，考虑走到某个地方能否使得答案是减少的，可以确定该答案是一个区间，在不断缩小后即可以得到答案

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
vector<int>v[N];
bool prime[N];
ll w[N];
ll sum[N];
void pre(int n)
{
    for(int i=2;i<=n;i++){
        if(!prime[i]){
            for(int j=i;j<=n;j+=i){
                if(i!=j)prime[j]=1;
                int tmp=j;
                while(tmp%i==0){
                    tmp/=i;
                    v[i].push_back(j);
                    sum[j]++;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        sum[i]+=sum[i-1];
    }
}
void work()
{
    pre(1e5);
    int n;
    while(~scanf("%d",&n)){
        ll cnt=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&w[i]);
            cnt-=w[i];
            w[i]+=w[i-1];
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ans+=(w[i]-w[i-1])*sum[i];
        }
        int l=1,r=n;
        for(int i=n;i>=2;i--){
            if(!prime[i]){
                for(int j=0;j<v[i].size();j++){
                    int x=v[i][j];
                    if(x>n)break;
                    if(x>l){
                        ll tmp=(w[x-1]-w[l-1])*2;
                        if(cnt+tmp>=0){
                            if(r>=x){
                                cnt+=(w[r]-w[x-1])*2;
                                r=x-1;
                            }
                            break;
                        }
                        cnt+=tmp;
                        l=x;
                    }
                    //printf("%d\n",ans);
                    ans+=cnt;
                }
                if(cnt>=0)break;
            }
        }
        printf("%lld\n",ans);
    }

}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}