『算法-ACM 竞赛-数学-数论』HDU6919 Senior PanⅡ【2017 多校第九场】

Description

给出一个区间[L,R][L,R]，问该区间中所有以 KK 作为最小因子（大于 11 的）的数字之和

Input

第一行输入一整数 TT 表示用例组数，每组用例输入三个整数 L,R,KL,R,K(1≤L≤R≤1011,2≤K≤1011)(1≤L≤R≤1011,2≤K≤1011)
Output

对于每组用例，输出答案，结果模 109+7109+7
Sample Input

2
1 20 5
2 6 3

Sample Output

Case #1: 5
Case #2: 3

先放网上的通解，就是大致的思路。

看题解看的心累。
然后是我写的题解：

然后是代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define inv2 500000004
const int  Max=320000,Max_R=14000,cnt=5000;
int tot=0,p[Max+5],flag[Max+5],dp[Max_R+5][cnt+5];
int ins(int x,int y) //防溢出加法
{
    return x+y>=mod?x+y-mod:x+y;
}
int des(int x,int y)//防溢出减法
{
    return x-y<0?x-y+mod:x-y;
}
void init()
{
    for(int i=2;i<=Max;i++)
        if(!flag[i])
        {
            p[++tot]=i;
            for(int j=2*i;j<=Max;j+=i)flag[j]=1;
        }
    dp[0][0]=0;
    for(int i=1;i<=Max_R;i++)
    {
        dp[i][0]=ins(dp[i-1][0],i);
        for(int j=1;j<=cnt;j++)
            dp[i][j]=des(dp[i][j-1],(ll)p[j]*dp[i/p[j]][j-1]%mod);
    }
}
bool check(ll n)//素数检测
{
    for(int i=1;i<=tot&&(ll)p[i]*p[i]<=n;i++)
        if(n%p[i]==0)return 0;
    return 1;
}
int DFS(ll n,int m)
{
    if(n<2)return n;
    if(m==0)
    {
        n%=mod;
        return n*(n+1)%mod*inv2%mod;
    }
    if(n<=Max_R&&m<=cnt)return dp[n][m];//在IJ区间可以直接出答案
    if(n<=p[m])return 1;
    return des(DFS(n,m-1),(ll)p[m]*DFS(n/p[m],m-1)%mod);//不在IJ区间不能直接出答案
}
int main()
{
    init();
    int T,Case=1,pos;
    scanf("%d",&T);
    while(T--)
    {
        ll L,R,K;
        scanf("%I64d%I64d%I64d",&L,&R,&K);
        printf("Case #%d: ",Case++);
        if(!check(K))printf("0\n");
        else if(K>Max)
        {
            if(K>=L&&K<=R)printf("%d\n",K%mod);
            else printf("0\n");
        }
        else
        {
            for(pos=1;p[pos]<K;pos++);
            pos--;
            int ans=des(K*DFS(R/K,pos)%mod,K*DFS((L-1)/K,pos)%mod);
            printf("%d\n",ans);
        }
    }
    return 0;
}