fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define lli long long int
  3. #define ulli unsigned long long int
  4. using namespace std;
  5.  
  6. ulli l,r,p,q;
  7. vector<ulli> vp,vq;
  8.  
  9. ulli gcd(ulli x, ulli y)
  10. {
  11. 	if (y>x) swap(x,y);
  12. 	while (y)
  13. 	{
  14. 		ulli r = x%y;
  15. 		x = y;
  16. 		y = r;
  17. 	}
  18. 	return x;
  19. }
  20.  
  21. ulli lcm(ulli x , ulli y)
  22. {
  23. 	ulli g = gcd(x,y);
  24. 	ulli X = x / g;
  25. 	ulli Y = y;
  26.  
  27. 	ulli M = (ulli)(1e18)/X;
  28. 	if ( Y > M ) return -1;		// not valid
  29. 	X *= Y;
  30. 	return X;
  31. }
  32.  
  33. ulli f(ulli n)
  34. {
  35. 	ulli ans = 0;
  36. 	int vps = vp.size() , vqs = vq.size();
  37.  
  38. 	for (int i=vps-1 ; i>0 ; i--)
  39. 	{
  40. 		if (vp[i] > n) continue;
  41. 		ulli that = (i==vps-1 ? 0 : n/vp[i+1]);
  42. 		ulli thiz = n/vp[i];
  43. 		ulli cnt = thiz - that;
  44. 		ans += cnt;
  45.  
  46. 		if (i < vqs)
  47. 		{
  48. 			if (vq[i]>n) continue;
  49. 			ulli b = lcm(vp[i] , vq[i]);
  50. 			if (b==-1) continue;
  51. 			ans -= n/b;
  52. 			if (i!=vps-1)
  53. 			{
  54. 				ulli b2 = lcm(vp[i+1] , b);
  55. 				if (b2==-1) continue;
  56. 				ans += n/b2;
  57. 			}
  58. 		}
  59. 	}
  60.  
  61. 	return ans;
  62. }
  63.  
  64. int main ()
  65. {
  66. 	cin>>l>>r>>p>>q;
  67.  
  68. 	for(ulli i=1,e=(r/p) ; 1 ; i*=p) { vp.push_back(i); if (i>e) break; } 
  69. 	for(ulli i=1,e=(r/q) ; 1 ; i*=q) { vq.push_back(i); if (i>e) break; } 
  70.  
  71. 	ulli L = f(l-1);
  72. 	ulli R = f(r);
  73.  
  74. 	cout<<(R-L);
  75.  
  76.     return 0;
  77. }
Runtime error #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YVbmOt
language:
C++14 (gcc 8.3)
created:
9 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!