fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll MOD = 1000000007;
  5. int prime[5000005];
  6. long long ff[5000005];
  7. ll l,r,t;
  8.  
  9. void seive(){
  10. 	for(int i=2;i<5000005;i++)prime[i] = -1;
  11. 	prime[0]= prime[1] = 0;
  12. 	for(long i=2;i*i<=5000005;i++){
  13. 		if(prime[i]==-1){
  14. 			for(long j= i+i;j<=5000005;j+=i)
  15. 				if(prime[j]==-1)
  16. 					prime[j] = i;
  17. 		}
  18. 	}
  19. }
  20. void solv(){
  21. 	ff[1] = 0;
  22. 	for(long i=2;i<=r;i++){
  23. 		if(prime[i]!=-1){
  24. 			ff [i] = ((i/prime[i] * ff[prime[i]])%MOD + ff[i/prime[i]])%MOD;
  25. 		}
  26. 		else {
  27. 			ff[i] = ((i-1) * i /2 )% MOD;}
  28. 	}
  29. }
  30. int main(){
  31. 	ll ans = 0,k=1;
  32. 	cin>>t>>l>>r;
  33. 	seive();
  34. 	solv();
  35. 	for(int i = l;i<=r;i++){
  36. 		ans = (ans + (k * ff[i]) % MOD) % MOD;
  37. 		k = (t * k)%MOD;
  38. 	}
  39. 	cout<<ans<<endl;
  40. 	return 0;
  41. 	}
  42.  
Success #stdin #stdout 0.18s 73792KB
comments (?)
stdin 
7 2444902 2613424
stdout 
619309304
https://ideone.com/IJiZ5U
language:
C++14 (gcc 8.3)
created:
7 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!