fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. #define FOR(i,a,b,k) for (ll i=a;i<=b;i+=k)
  3. #define FORD(i,a,b,k) for (ll i=a;i>=b;i-=k)
  4. #define pb(i) push_back(i)
  5. #define ll long long int
  6. #define MOD 1000000007
  7. #define lim 1e16
  8. #define F first
  9. #define S second
  10. using namespace std;
  11. ll l,r;
  12.  
  13. vector<ll> p;
  14. vector<bool> a(1e7,0);
  15.  
  16. unordered_map<ll,ll> m,v;
  17.  
  18. void sieve()
  19. {
  20. 	p.pb(2);
  21. 	FOR(i,3,1e7,2) 
  22. 	{
  23. 		if(a[i]==0) 
  24. 		{
  25. 			p.pb(i);
  26. 			FOR(j,i*3,1e7,i*2) a[j]=1;
  27. 		}
  28. 	}
  29. }
  30.  
  31. void loading()
  32. {
  33. 	FOR(i,l,r,1)
  34. 	{
  35. 		m[i]=i;
  36. 	}
  37.  
  38. 	for(auto i:p) 
  39. 	{
  40. 		FOR(j,(l+i-1)/i*i,r,i)
  41. 		{
  42. 			ll c=0;
  43. 			while(m[j]%i==0) 
  44. 			{
  45. 				m[j]/=i;
  46. 				c++;
  47. 			}
  48. 			v[i]=max(v[i],c);
  49. 		}
  50. 	}
  51.  
  52. 	ll res=1;
  53. 	for(auto x:v) 
  54. 	{
  55. 		ll k=pow(x.F,x.S);
  56. 		res=((res%MOD)*(k%MOD))%MOD;
  57. 	}
  58. 	for(auto x:m) res=((res%MOD)*(x.S%MOD))%MOD;
  59.  
  60. 	cout<<res;
  61. }
  62.  
  63. int main()
  64. {
  65.     	ios_base::sync_with_stdio(false);
  66.         cin.tie(NULL);cout.tie(NULL);
  67.     cin>>l>>r;    
  68.     sieve();
  69.     loading();
  70.     return 0;
  71. }
Time limit exceeded #stdin #stdout 5s 14668KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NfXHwi
language:
C++ (gcc 8.3)
created:
2 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!