fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. #define sz(v) ((int)v.size())
  5. #define rep(i,n) for(int i = 0; i < (int)(n); ++i)
  6. #define repi(n)  for(int i = 0; i < (int)(n); ++i)
  7. #define repj(n)  for(int j = 0; j < (int)(n); ++j)
  8. #define fast_scan() (ios_base::sync_with_stdio(false),cin.tie(NULL))
  9. typedef long long ll;
  10. typedef vector<ll> vl;
  11. ll gcd(ll x, ll y)
  12. {
  13. 	ll temp;
  14. 	if (y > x) swap(x, y);
  15. 	while (y != 0) temp = y, y = x % y, x = temp;
  16. 	return x;
  17. }
  18. ll lcm(ll a, ll b)
  19. {
  20. 	return  a / gcd(a, b) * b;
  21. }
  22. ll multi_lcm(vector<ll> &numbers, int i)
  23. {
  24. 	if (i <= 0) return numbers[i];
  25.  
  26. 	return lcm(numbers[i], multi_lcm(numbers, i - 1));
  27. }
  28. ll divisibles(ll n, ll m, vl &nums)
  29. {
  30. 	ll LCM = multi_lcm(nums, sz(nums) - 1);
  31. 	return m / LCM - n / LCM + (n % LCM == 0 ? 1 : 0);
  32. }
  33. int main()
  34. {
  35. 	fast_scan();
  36. 	int t;
  37. 	cin >> t;
  38. 	rep(T, t)
  39. 	{
  40. 		ll n, m, a, d;
  41. 		cin >> n >> m >> a >> d;
  42. 		vl nums;
  43. 		repi(5) nums.push_back(a + i * d);
  44. 		ll ans = 0;
  45. 		int pw = 1 << 5;
  46.  
  47. 		repi(pw)
  48. 		{
  49. 			vl combination;
  50. 			repj(5) if ((i >> j) & 1 == 1) combination.push_back(nums[j]);
  51. 			if (sz(combination) != 0)
  52. 			{
  53. 				ll divisibles_num = divisibles(n, m, combination);
  54. 				if (sz(combination) & 1) ans += divisibles_num; else ans -= divisibles_num;
  55. 			}
  56. 		}
  57. 		cout << (m - n + 1) - ans << endl;
  58. 	}
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
9

1 10 2 2

20 100 3 3

100 1000 4 5
107 112 6 1
1 40 4 1
1 100 4 33
1 100 6 2
1 1 1 1
1 2 3 4
stdout
copy 
5
54
543
3
19
72
68
0
2
https://ideone.com/SoQ4zU
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!