fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define ll long long
  9. #define uint unsigned int
  10. #define ull  unsigned long long
  11. #define pb push_back
  12. #define mk make_pair
  13. #define ins insert
  14. #define all(x) (x).begin(), (x).end()
  15. #define rall(x) (x).rbegin(),(x).rend()
  16. #define X first
  17. #define Y second
  18. #define umap unordered_map
  19. #define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  20. #define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
  21. #define mset multiset
  22. #define pqueue priority_queue
  23.  
  24. template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  25.  
  26. const int  N = 2e5 + 314;
  27. const int INF = 1e9;
  28. const double PI = acos(-1);
  29. const int MOD = 1e9 + 7;
  30. const double eps = 1e-9;
  31. const long long LINF = 1e18 + 3141;
  32. ll a, b, q; 
  33. ll get(ll x) {
  34.     ll l = a * b / __gcd(a, b);
  35.     ll ans = min(b - 1, x);
  36.     ll k = x / l;
  37.     if(k > 0){
  38.         ans += (k - 1) * (b);
  39.         ans += min(b, x - k * l + 1);
  40.     }
  41.  
  42.     return ans;
  43.  
  44. }
  45. void solve(){  
  46.     cin >> a >> b >> q;
  47.     if(a >= b)
  48.         swap(a, b);
  49.     while(q --) {
  50.         ll l, r;
  51.         cin >> l >> r;
  52.         cout << r - l + 1 - (get(r) - get(l - 1)) << " ";
  53.     }
  54.     cout << "\n";
  55.  
  56. }
  57.  
  58. int main(){
  59.     speed();
  60.     int t = 1;
  61.     cin >> t;
  62.     while(t--)solve();
  63. }
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/VTSzgt
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
4 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!