ABC150 D Semi Common Multiple

ABC150 D Semi Common Multiple

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/abc150/tasks/abc150_d

考察

• 式変形すると，となる
• X=になるのでXはの倍数であり，で割った商が奇数となるものになる
• なので，の最小公倍数を求めて，それをで割った商が1つでも偶数になるならダメ，それ以外は個ある

ソースコード

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

typedef long long int ll;

/******************************************************************************************/



//ユークリッド互除法
template<typename T>
T gcd(T x, T y) {

	if (y == 0) {
		return x;
	}
	else {
		return gcd(y, x % y);
	}
}

/*最小公倍数*/
template<typename T>
T lcm(T x, T y) {
	T tmp = gcd(x, y);

	return x /tmp * y;
}


int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);


	ll n, m;
	cin >> n >> m;
	ll ans = 0;
	vector<ll> a(n);

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		a[i] /= 2;
	}
	ll hoge = a[0];

	for (int i = 0; i < n; i++)
	{
		hoge = lcm(hoge, a[i]);
		if (hoge > m) {
			cout << 0 << endl;
			return 0;
		}
	}

	bool flag = true;
	for (int i = 0; i < n; i++)
	{

		if ((hoge / a[i]) % 2 == 0) {
			flag = false;
		}
	}

	if (flag) {
		cout << (m / hoge + 1) / 2 << endl;
	}
	else
	{
		cout << 0 << endl;
	}


	return 0;
}