题目大意：

首先定义f(n):有n个人参加比赛，可以进行任意轮的比赛，每一轮是将他们分成任意组（必须保证每组人数相同），然后每组的所有人两两之间都必须进行一次比较。f(n)就表示确定第一名所需的最少比较次数。

现在给你：l,r,t，让你求：

∑ i=l r t i−l ∗f(i) 
。

分析：

首先说明f(x)的求法：

f(x)=⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ xk ∗(k)∗(k−1)2 +f(xk )(k)∗(k−1)2  x不为质数x为质数 （k表示x的不为1的最小因子） 

这也就是等价于，如果一个数x可以质因数分解成： q 1 ≤q 2 ≤q 3 ≤...≤q n   。那么最优的比赛方法就是，先每一组是 q 1   人，下一轮每一组是 q 2   人，以此方法直到最后找到胜者。

下面证明该贪心策略的正确性：

首先，证明“假如一个数 x  可以表示成两个整数 q 1 ,q 2   的乘积，那么每组 x  人一定不如首先每组 q 1   人，下一轮每组 q 2   人”：

如果每组x人，那么比赛次数为： f 1 (x)=(x−1)∗x2 =(q 1 q 2 −1)q 1 q 2 2   ；
如果先 q 1   再 q 2   人，那么比赛次数为： f 2 (x)=f 2 (q 1 q 2 )=q 2 ((q 1 −1)q 1 2 )+(q 2 −1)q 2 2   ；
那么： f 1 (x)−f 2 (x)=q 2 (q 2 −1)(q 2 1 −1)2 ≥0 

这就说明分成两次比赛次数更少。证毕~

其次，证明“假如 q 1 >q 2   ，那么先分成 q 2   组，再分成$$q_1组比赛，总比赛次数更少”：

如果先 q 1   后 q 2   那么比赛次数a为： a=q 2 (q 1 −1)q 1 2 +(q 2 −1)q 2 2   ；
如果先 q 2   后 q 1   那么比赛次数a为： a=q 1 (q 2 −1)q 2 2 +(q 1 −1)q 1 2   ；
则： a−b=(q 1 −1)(q 2 −1)(q 1 −q 2 )2 >0 

这就说明对于每一轮尽量使每组人数更小才能使得总比赛次数最少。证毕~

综合以上连个结论，我们就得到了贪心策略。

然后就是如何更快的求出一段连续的f(x)的值：

这里有点 类似于线性筛素数的方法，每次枚举当前最小的素数的整数倍，同时对 f(x)  的值进行对应的类加操作，程序中我用了一个 f_full [ i ] 数组表示当前 i 还剩多少未被除净。

代码：

#include<bits/stdc++.h>
#define maxn 5000500
#define mod 1000000007
using namespace std;

long long int t;
int l,r;
long long int t_pow[maxn],f[maxn],f_full[maxn];
int is_prime[maxn];
//bool appear[maxn];
void init()
{
    for(int i=0;i<maxn;i++)
    {
        f[i]=0;f_full[i]=(long long int)i;
        is_prime[i]=1;
    }
}

void init_t()
{
    t_pow[0]=1;
    for(int i=1;i<=r-l;i++)
    {
        t_pow[i]=t_pow[i-1]*t;
        t_pow[i]%=mod;
        //cout<<t_pow[i]<<endl;
    }
}
/*void test() { //memset(appear,0,sizeof(appear)); int num=0; for(int i=1;i<=r;i++) { int flag=0; for(int j=2;j<sqrt(i)+1;j++) { if(i%j==0) { flag=1;break; } } if(flag==0) { num++; //appear[i]=1; //cout<<i<<" "; } } cout<<"num="<<num<<endl; } */
void init_f()
{
    for(int i=2;i<=r;i++)
    {
        if(is_prime[i]==1)//i是质数
        {
            int k=2;
            f[i]=(long long int)i*(long long int)(i-1)/2;
            f[i]%=mod;
            f_full[i]=1;
            while(i*k<=r)
            {
                int temp=i*k;k++;
                is_prime[temp]=0;//筛素数
                while(f_full[temp]%(long long int )i==0)
                {
                    f_full[temp]/=(long long int)i;
                    f[temp]+=(((f_full[temp])*(((long long int)i*(long long int)(i-1)/2)%mod))%mod);
                    f[temp]%=mod;
                }
            }
        }

    }
}

int main()
{

    scanf("%lld%d%d",&t,&l,&r);
    //test();
    init();
    init_t();
    init_f();
    long long int ans=0;
    for(int i=0;i<=r-l;i++)
    {
        //printf("t[%d]=%lld f[%d]=%lld f_full[%d]=%lld\n",i,t_pow[i],l+i,f[l+i],i+l,f_full[i+l]);
        ans=ans+t_pow[i]*f[l+i];
        ans%=mod;
    }
    printf("%I64d\n",ans);
}