CF822D My pretty girl Noora 题解

· · 题解

乍一看题目所求的式子还以为是什么神奇的推式子题，其实就是把f(l)到f(r)分别求出来，是个最优化问题。

DP式很方便得出：f(i)=\mathop{min}\limits_{d|i}\{f(\frac{i}{d})\times\frac{i}{d}\times\frac{d(d-1)}{2}\}

不是常规的DP方程，官方题解给了枚举因数转化为枚举倍数的优化，做到了log级别，我们尝试观察最优化目标本身。

第一个问题，一个数拆的次数多好，还是少好？

我们简单比较两个式子即可：k\times\frac{ab-1}{2}和k\times\frac{a-1}{2}+\frac{k}{a}\times\frac{b-1}{2}。进行一些简单的化简发现前者恒大于后者。故拆的次数越少越好，于是DP式中不需枚举约数，枚举素因数即可。

第二个问题，先拆出来的素因数大好，还是小好？

同样比较两个式子（不妨设a>b）：k\times\frac{a-1}{2}+\frac{k}{a}\times\frac{b-1}{2}和k\times\frac{b-1}{2}+\frac{k}{b}\times\frac{a-1}{2}。化简同样不难，作差法，因式分解后即观察(a-b)(a-1)(b-1)的正负，显然为正，于是先拆出来的素因数小好，DP式得到了最终的化简f(i)=f(\frac{i}{p_{min}})+ i \times\frac{(p_{min}-1)}{2}

最优化问题转化为了求一个数的最小质因数，考虑到线性筛中所有合数正用的是它最小素因数筛掉的，于是我们另开一个数组记录p_{min}即可。

总时间复杂度O(r)。爆踩标算(bushi

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll t,l,r;

const int maxn = 5e6+5;
const ll mod = 1e9+7;

int prime[maxn],pt,sm[maxn];

void shai(){
    for(int i=2;i<=maxn-5;i++){
        if(!vst[i]) prime[++pt]=i;
        for(int j=1;j<=pt&&i*prime[j]<=maxn-5;j++){
            vst[i*prime[j]]=1;
            sm[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
}

ll f[maxn],ans;

int main(){

    shai();
    cin>>t>>l>>r;
    for(int i=2;i<=r;i++){
        if(!sm[i]) sm[i]=i;
        f[i]=f[i/sm[i]]+((ll)i*((ll)sm[i]-1)/2)%mod;
        f[i]%=mod;
    }
    ll nw=1;
    for(int i=l;i<=r;i++){
        ans+=nw*f[i]%mod;
        ans%=mod;
        nw=nw*t%mod;
    }
    cout<<ans;
    return 0;
}