题目：找出【L,R】内，所有n*k的和，n为1或者是大于等于k的质数；
思路：遇到很多次二次筛的，再次遇到还是忘记了反向思维，在此，我们不去找符合的情况，而是去寻找不符合的情况，因为符合的情况太难找，不符合的就很好找了，用K以下的质数去筛就可以了，考虑到当k>320000的时候，k^2超出数据范围，所以，这种情况要么只有K自己，要么没有，那么考虑k<320000的情况，在此我们只需要找出相应的n即可，定义一个 dp[i][j]表示1~i 这 i个数被前j个素数筛过以后剩下的数的和。
则：
dp[i][j]=dp[i][j−1]−pri[j]∗dp[i/pri[j]][j−1]
解释：对于dp[i][j]，只需要考虑在dp[i][j−1]的基础上减去第j个素数造成的影响。
对于[1,i]中一个会被第j个素数pri[j]筛去的数来说，其可以表示成p∗pri[j]
其中p<=i/pri[j]，因为其不会被j−1个素数筛去，故dp[i/pri[j]][j−1]中的每一个数，乘上pri[j]之后一定就是那个会被第j个素数筛去的数，故递推式即为所求。
小范围时候记忆化以下，可以快200ms左右，不记忆化也可以过；注意计算中间爆LL那种情况即可，代码：
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const LL mod=1e9+7; const int maxn=4e5+10; LL prim[28000]; LL dp[10001][101]; bool p[maxn]; LL l,r,k; int siever() { for(int i=0;i<300;i++) for(int k=(i<<1)+3,j=k*i+k+i;j<160010;j+=k) p[j]=1; int sp=1; for(int i=0;i<160010;i++) if(!p[i])prim[sp++]=(i<<1)+3; prim[0]=2; return sp; } bool isprim(LL num) { if(num==2)return true; if(!(num&1))return false; if(num<320000) if(!p[(num-3)>>1])return true; else return false; for(int i=0;prim[i]<320010;i++) if(num%prim[i]==0)return false; return true; } LL f(LL i,int j) { if(i<=1)return i; if(j==-1)return (i+1)%mod*(i%mod)%mod*500000004%mod; while(prim[j]>i&&j)j--; if(i<10001&&j<101) if(dp[i][j]!=-1)return dp[i][j]; else return dp[i][j]=f(i,j-1)-prim[j]*f(i/prim[j],j-1)%mod; return f(i,j-1)-prim[j]*f(i/prim[j],j-1)%mod; } int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int si=siever(); memset(dp,-1,sizeof dp); int T,cas=0;scanf("%d",&T); while(T--) { scanf("%lld%lld%lld",&l,&r,&k); if(k>r || !isprim(k)){printf("Case #%d: 0 ",++cas);continue;} if(k>320000) if(k>=l)printf("Case #%d: %lld ",++cas,k%mod); else printf("Case #%d: 0 ",++cas); else { int j=lower_bound(prim,prim+si,(int)k)-prim; LL ans=f(r/k,j-1)*k%mod-f((l-1)/k,j-1)*k%mod; printf("Case #%d: %lld ",++cas,(ans%mod+mod)%mod); } } return 0; }