题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6169
题意:给了区间L,R,求[L,R]区间所有满足其最小质数因子为k的数的和。
解法:
我参考的这篇blog。http://blog.csdn.net/wubaizhe/article/details/77484454#cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
const int Mx = 320000;
const int A = Mx + 10;
const int B = 1e4+10;
const int C = 1e2+10;
const LL inv = 500000004;
LL dp[B][C];
//dp[i][j]表示1~i 这 i个数被前j个素数筛过以后剩下的数的和。
//dp[i][j]=dp[i][j−1]−pri[j]∗dp[i/pri[j]][j−1]
int prime[A],tot;
bool isprime[A];
void predeal(){
tot=0;
memset(isprime, 1, sizeof(isprime));
for(LL i=2; i<A; i++){
if(isprime[i]){
for(LL j=i+i; j<A; j+=i){
isprime[j]=0;
}
}
}
for(int i=2; i<A; i++){
if(isprime[i]) prime[++tot] = i;
}
for(int i=1; i<B; i++)
{
dp[i][0] = 1LL*i*(i+1)/2%mod;
for(int j=1; j<C; j++)
{
dp[i][j] = (dp[i][j-1] - prime[j]*dp[i/prime[j]][j-1]%mod + mod)%mod;
}
}
}
LL dfs(LL n, LL m)
{
if(n<=1) return n;
if(!m) return n%mod*(n%mod+1)%mod*inv%mod;
if(n<B&&m<C) return dp[n][m];
if(prime[m]>n) return 1;
return (dfs(n,m-1)-prime[m]*dfs(n/prime[m],m-1)%mod+mod)%mod;
}
bool check(LL x){
for(LL i=2; i*i<=x; i++){
if(x%i==0){
return false;
}
}
return true;
}
int main()
{
predeal();
int T,ks=0;
scanf("%d", &T);
while(T--)
{
LL L,R,k;
scanf("%lld%lld%lld", &L,&R,&k);
printf("Case #%d: ", ++ks);
if(!check(k)){
puts("0");
}
else if(k>Mx){
if(L<=k&&k<=R) printf("%lld\n",k%mod);
else puts("0");
}
else{
int now=0;
while(prime[now+1]<k) now++;
LL ans = (dfs(R/k,now)*k%mod-dfs((L-1)/k,now)*k%mod + mod)%mod;
if(ans < 0) ans+=mod;
printf("%lld\n", ans);
}
}
return 0;
}