fork download
copy 
  1. #include<bits/stdc++.h>
  2. const int M=1e7;
  3. const int MD=1e9+7;
  4. using namespace std;
  5. typedef long long ll;
  6. ll p[M];
  7. bool ans[M];
  8. int dig(int n)
  9. {
  10. 	int su=0;
  11. 	while(n>0)
  12. 	{
  13. 		su+=n%10;
  14. 		n=n/10;
  15. 	}
  16. 	return su;
  17. }
  18. void sieve()
  19. {
  20. 	for(int i=2;i*i<=M;i++)
  21. 	{
  22. 		if(ans[i]) continue;
  23. 		p[i]=dig(i);
  24. 		for(int j=i+i;j<=M;j+=i)
  25. 		{
  26. 		   ans[j]=true;
  27. 		   p[j]=(p[j]+p[i])%MD;
  28. 		}
  29. 	}
  30. 	for(int i=1;i<=M;i++)
  31. 	p[i]=(p[i]+p[i-1])%MD;
  32. }
  33. int main() {
  34. 	sieve();
  35. 	int t;
  36. 	cin>>t;
  37. 	while(t--)
  38. 	{
  39. 		int l,r;
  40. 		cin>>l>>r;
  41. 		cout<<(p[r]-p[l-1]+MD)%MD<<endl;
  42. 	}
  43. 	return 0;
  44. }
Success #stdin #stdout 0.36s 103936KB
comments (?)
stdin
copy 
2
3 8
stdout
copy 
24
24
https://ideone.com/7D4Bvs
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!