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;
}