题目大意：

多组测试数据，每组给你三个数：l,r,k;让你输出区间 [ l , r ] 内所有最小不为 1 的因数是 k 的数的和。 （l,r,k≤1011）

分析：

  • 首先，如果 k 不是素数，那么肯定答案是 0 ，此处特判。

  • 其次，如果要想，如果 k 和比 k 大的第一个质数的乘积大于 r ，那么，只有 k 是区间 [ l , r ] 里唯一一个满足该条件的，所以答案为 k ，此处再次特判。

  • 最后，剩下的情况就只有 k≤sqrt(111) 约等于3e5的情况了。

下面就考虑 k<3∗105 的时候。

dp建立：

  • 状态确定：用 dp(i,j) 表示，区间 [ 1 , i ] 被前 j 个质数筛过之后，剩下的所有数的和。

  • 状态转移方程： dp(i,j)=dp(i,j−1)−pri(i)∗dp(ipri(j),j−1);

  • 边界：那么对于给定的 l,r,k ;答案就是： (dp(r,num(k)−1)−(dp(r,num(k)))−(dp(l−1,num(k)−1)−dp(l−1,num(k)))

  • 也就是： ans=k∗(dp(rk,num(k)−1)−dp(l−1k,num(k)−1)) ;

外加搜索：

状态数： 111∗3∗104=3∗1015

这么大的状态肯定是存不开的，所以我们选择初始化记录其中部分常用状态，其他状态通过搜索得到。现在就考虑哪些状态比较常用。

可以看到，在搜索 dp(i,j) 的时候， i 是很快减少的， j 是 1 个一个减少的，那么我觉得记录每一个 j 和比较小的 i

是比较划算的。那么我决定记录 dp(150,3∗104)

代码：

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

long long int dp[150][p_num]={0};
long long int prime[p_num]={0};
bool is_pim[maxn]={0};
long long int l,r,k;

int is_prime(long long int x)
{
    for(int i=0;i<p_num;i++)if(prime[i]==x)return i;
    return -1;
}
void init()//筛素数，
{
    for(int i=0;i<150;i++)for(int j=0;j<p_num;j++)dp[i][j]=-1;
    for(int i=2;i<maxn;i++)is_pim[i]=1;
    for(int i=2;i<maxn;i++)
    {
        if(is_pim[i]==1)
        {
            int t=2*i;
            while(t<maxn)
            {
                is_pim[t]=0;
                t+=i;
            }
        }
    }
    int num=1;
    for(int i=2;i<maxn;i++)
    {
        if(is_pim[i]==1)
        {
            prime[num]=i;num++;//cout<<i<<" ";
        }
    }
    //cout<<num;
}
long long int f(long long int i,long long int j)
{
    if(i==0)return 0;
    if(j==0)
    {
        if(i%2==0)return (((i/2)%mod)*((i+1)%mod))%mod;
        else return ((((i+1)/2)%mod)*(i%mod))%mod;
    }
    if(i<150&&j<maxn)
    {
        //if(j==0)return i;
        if(dp[i][j]==-1)
        {
            dp[i][j]=f(i,j-1)-(prime[j]*f(i/prime[j],j-1))%mod;
            dp[i][j]=(dp[i][j]+mod)%mod;
        }
        return dp[i][j];
    }
    return (f(i,j-1)-prime[j]*f(i/prime[j],j-1)%mod+mod)%mod;
}
bool is_p(long long int x)
{
    int y=sqrt(x);
    for(int i=2;i<=y;i++)
    {
        if(x%i==0)return 0;
    }
    return 1;
}

int main()
{
    int test=0,cass=0;
    init();
    scanf("%d",&test);
    while(test--)
    {
        cass++;
        scanf("%lld%lld%lld",&l,&r,&k);
        if(k>=maxn)
        {
            printf("Case #%d: %lld\n",cass,(l<=k&&k<=r&&is_p(k))?(k%mod):0);continue;
        }
        int w=is_prime(k);
        if(w==-1)
        {
            printf("Case #%d: 0\n",cass);continue;
        }
        printf("Case #%d: %lld\n", cass , (k * ( f(r/k,w-1)-f((l-1)/k,w-1) )%mod+mod)%mod );
    }
}