Codeforces 822D My pretty girl Noora(最小素因子的性质)

题目大意：一场选美比赛有N个人，可以分成N/x,每组x人。每组的比较次数为x（x-1）/2，f[N]为最后决出冠军所需的比较次数，可以通过改变x的值使f[N]改变。题目给出t,l,r(1 ≤ t < 109 + 7, 2 ≤ l ≤ r ≤ 5·106)。求 t^0⋅f(l)+t^1⋅f(l+1)+⋯+t^r−l⋅f(r) 的最小值对1e9+7的模。

解题思路：①如果人数为素数，那f[N]=N(N-1)/2;

　　　　　②如果不是素数，那就找出最小素因子x,分成N/x，每组x人，f[N]=N/x*f[x]+f[N/x]。

　　　　　关于②，比如6可以分为3个2或者2个3，所需比较数分别是5和7，显然分的组数越多越好。还有关于为什么加上f[N/x]，因为是递推的，所以f[N/x]肯定也是最小的，不用担心N/x不是素数还要在进行分组的问题。

代码：

#include<iostream>
using namespace std;
typedef long long ll;
const int N=5e6+5;
const ll MOD=1e9+7; 
bool prime[N];
ll p[N];
ll f[N];
int cnt;
//素数表 
void is_prime(){
    for(int i=2;i<=N;i++)
        prime[i]=true;
    for(int i=2;i*i<=N;i++){
        if(prime[i]){
            p[cnt++]=i;
            for(int j=i*i;j<=N;j+=i){
                prime[j]=false;
            }
        }    
    }
}

int main(){
    is_prime();
    f[1]=0;
    for(int i=2;i<N;i++){
        //判断是否为素数 
        if(prime[i]){
            f[i]=((ll)i*(i-1)/2)%MOD;
        }
        else{
            //找最小素因子 
            ll factor;
            for(int j=0;j<cnt;j++){
                if(i%p[j]==0){
                    factor=p[j];
                    break; 
                }                
            }    
            f[i]=(i/factor*f[factor]+f[i/factor])%MOD;
        }
    }
    ll ans=0;
    ll t,l,r;
    cin>>t>>l>>r;
    for(int i=r;i>=l;i--){
        ans=(ans*t)%MOD;
        ans=(ans+f[i])%MOD;
    }
    cout<<ans<<endl; 
}