Ideone.com

fork download

copy

#include<iostream>
#include<vector>
using namespace std;
#define sz(v) ((int)v.size())
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define repi(n)  for(int i = 0; i < (int)(n); ++i)
#define repj(n)  for(int j = 0; j < (int)(n); ++j)
#define mem(a,x) memset(a,x,sizeof(a))
typedef long long ll;
 
ll gcd(ll x, ll y)
{
	ll temp;
	if (y > x)
	{
		temp = x;
		x = y;
		y = temp;
	}
	while (y != 0)
	{
		temp = y;
		y = x % y;
		x = temp;
	}
	return x;
}
ll lcm(ll a, ll b)
{
	return  a / gcd(a, b) * b;
}
ll multi_lcm(vector<ll> &numbers, int i)
{
	if (i <= 0) return numbers[i];
 
	return lcm(numbers[i], multi_lcm(numbers, i - 1));
}
 
int main()
{
	int t;
	ll n, m, a, d;
	cin >> t;
	rep(l, t)
	{
		cin >> n >> m >> a >> d;
		vector<int> nums;
		repi(5) nums.push_back(a + i* d);
        ll ans = 0;
		ll power = 1 << 5;
		repi(power)
		{
			vector<ll> permutations;
			repj(5) if ((i >> j) & 1 == 1) permutations.push_back(nums[j]);
			if (sz(permutations) != 0)
			{
				ll lCM = multi_lcm(permutations, sz(permutations) - 1);
			if (sz(permutations) & 1) ans += m / lCM  - n / lCM + ( n % lCM == 0 ? 1 : 0);
			else ans -= m / lCM  - n / lCM + ( n % lCM == 0 ? 1 : 0);
			}
 
		}
 
		cout << (m - n + 1) - ans << endl;
 
	}
	return 0;
}

Success #stdin #stdout 0.14s 4528KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/sqmt8Q

language:

C++14 (gcc 8.3)

created:

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language