#300949 (C++14) No.186 中華風 (Easy)

• 問題: No.186 中華風 (Easy)
• ユーザー: Aquarius
• 提出日時: 2018-12-02 22:38:25
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 9,099 bytes
• コンパイル時間: 807 ms
• コンパイル使用メモリ: 74,456 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-19 18:33:13
• 合計ジャッジ時間: 1,488 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
other	AC * 23

ソースコード

#include <vector>
#include <cstdint>

uint64_t GCD(uint64_t a, uint64_t b);
uint64_t LCM(uint64_t a, uint64_t b);

uint64_t GCD(const std::vector<uint64_t>& values);
uint64_t LCM(const std::vector<uint64_t>& values);

int64_t Extended_GCD(int64_t a, int64_t b, int64_t& x, int64_t& y);
std::pair<uint64_t, uint64_t> Extended_GCD_unsigned(uint64_t a, uint64_t b);
/* ax - by = c を解く関数を別に作ってもいいかも */

template <class T>
int Sign(T value);

template<class T>
inline int Sign(T value) {
	if (value > 0) return 1;
	if (value < 0) return -1;
	return 0;
}

template <class T>
T Pow(T base, uint64_t exp);

template <class T>
T Pow(T base, uint64_t exp) {
	T product = T(1);
	while (exp > 0) {
		if (exp & 0x1) {
			product *= base;
		}
		base *= base;
		exp >>= 1;
	}
	return product;
}


/* operator*(DynamicMod, uint) とかもあったほうがいいのかも */
class DynamicMod {
	uint64_t value_m;
	uint64_t mod_m;
public:
	DynamicMod();
	DynamicMod(uint64_t value, uint64_t mod);
	DynamicMod(const DynamicMod&) = default;

	DynamicMod& operator=(const DynamicMod&) = default;

	DynamicMod& operator+=(const DynamicMod& right);
	DynamicMod& operator-=(const DynamicMod& right);
	DynamicMod& operator*=(const DynamicMod& right);

	static bool Is_same_mod(const DynamicMod& left, const DynamicMod& right);
	static int Compare(const DynamicMod& left, const DynamicMod& right);

	uint64_t Get_value() const;
	uint64_t Get_mod() const;

	static DynamicMod Conjunction(const DynamicMod& a, const DynamicMod& b);
	static DynamicMod Conjunction(const std::vector<DynamicMod>& values);
	static DynamicMod Divide(const DynamicMod& a, const DynamicMod& b);
};

DynamicMod operator+(const DynamicMod& left, const DynamicMod& right);
DynamicMod operator-(const DynamicMod& left, const DynamicMod& right);
DynamicMod operator*(const DynamicMod& left, const DynamicMod& right);

bool operator==(const DynamicMod& left, const DynamicMod& right);
bool operator!=(const DynamicMod& left, const DynamicMod& right);
bool operator<(const DynamicMod& left, const DynamicMod& right);
bool operator<=(const DynamicMod& left, const DynamicMod& right);
bool operator>(const DynamicMod& left, const DynamicMod& right);
bool operator>=(const DynamicMod& left, const DynamicMod& right);

#ifdef ONLY_MY_ENVIR
#include "Math.h"
#endif

#include <numeric>
#include <cassert>
#include <stdexcept>

uint64_t GCD(uint64_t a, uint64_t b) {
	if (b == 0) return a;
	return GCD(b, a % b);
}

uint64_t LCM(uint64_t a, uint64_t b) {
	return a / GCD(a, b) * b;
}

uint64_t GCD(const std::vector<uint64_t>& values) {
	using FuncType = uint64_t (*)(uint64_t, uint64_t);
	return std::accumulate(values.begin(), values.end(), 0ULL, (FuncType)GCD);
}

uint64_t LCM(const std::vector<uint64_t>& values) {
	using FuncType = uint64_t(*)(uint64_t, uint64_t);
	return std::accumulate(values.begin(), values.end(), 1ULL, (FuncType)LCM);
}


/* ax + by = GCD(a, b) の整数解を求める
 * a > 1 || b > 1 のとき abs(x) <= b / (2g) && abs(y) <= a / (2g) を満たす (g = GCD(a, b))
 * 返り値は GCD(a, b) */
int64_t Extended_GCD(int64_t a, int64_t b, int64_t& x, int64_t& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	uint64_t ret = Extended_GCD(b, a % b, y, x);
	y -= (a / b) * x;
	return ret;
}

/* ax - by = GCD(a, b) の非負整数解を求める (x < b / g && y < a / g を満たす, g = GCD(a, b)) */
std::pair<uint64_t, uint64_t> Extended_GCD_unsigned(uint64_t a, uint64_t b) {
	assert(a != 0 && b != 0);

	/* もともとの方程式の解 (x, y) が、
	 * 現在の (a, b) についての ap - bq = 1 の解 (p, q) の一次式で
	 * (x, y) = mat * (p, q) と書ける(ように mat を定める) */
	uint64_t mat[2][2] = {
		{ 1, 0 },
		{ 0, 1 }
	};

	while (true) {
		if (a > b) {
			if (a % b == 0) return std::make_pair(
				mat[0][0] + (a / b - 1) * mat[0][1],
				mat[1][0] + (a / b - 1) * mat[1][1]
			);
			mat[0][0] += (a / b) * mat[0][1];
			mat[1][0] += (a / b) * mat[1][1];
			a %= b;
		} else {
			if (b % a == 0) return std::make_pair(mat[0][0], mat[1][0]);
			mat[0][1] += (b / a) * mat[0][0];
			mat[1][1] += (b / a) * mat[1][0];
			b %= a;
		}
	}
}

DynamicMod::DynamicMod()
	: DynamicMod(0, 1) {
}

DynamicMod::DynamicMod(uint64_t value, uint64_t mod)
	: value_m(value), mod_m(mod) {
	assert(mod != 0);

	if (value_m >= mod_m) {
		value_m %= mod_m;
	}
}

DynamicMod& DynamicMod::operator+=(const DynamicMod& right) {
	assert(Is_same_mod(*this, right));

	if (mod_m - value_m <= right.value_m) {
		value_m -= mod_m;
	}
	value_m += right.value_m;
	return *this;
}

DynamicMod& DynamicMod::operator-=(const DynamicMod& right) {
	assert(Is_same_mod(*this, right));

	if (value_m < right.value_m) {
		value_m += mod_m;
	}
	value_m -= right.value_m;
	return *this;
}

DynamicMod& DynamicMod::operator*=(const DynamicMod& right) {
	assert(Is_same_mod(*this, right));
	
	uint64_t product = 0;
	uint64_t addend = value_m;
	uint64_t multiplier = right.value_m;
	while (multiplier > 0) {
		if (multiplier & 0x1) {
			/* product += addend を mod を取りながら実行 */
			if (mod_m - product <= addend) {
				product -= mod_m;
			}
			product += addend;
		}

		/* addend += addend を mod を取りながら実行 */
		if (mod_m - addend <= addend) {
			addend += addend;
			addend -= mod_m;
		} else {
			addend += addend;
		}

		multiplier >>= 1;
	}
	value_m = product;

	return *this;
}

bool DynamicMod::Is_same_mod(const DynamicMod& left, const DynamicMod& right) {
	return left.mod_m == right.mod_m;
}

int DynamicMod::Compare(const DynamicMod& left, const DynamicMod& right) {
	if (left.mod_m < right.mod_m) return -1;
	if (left.mod_m > right.mod_m) return 1;
	if (left.value_m < right.value_m) return -1;
	if (left.value_m > right.value_m) return 1;
	return 0;
}

uint64_t DynamicMod::Get_value() const {
	return value_m;
}

uint64_t DynamicMod::Get_mod() const {
	return mod_m;
}

/* (中国剰余定理) */
DynamicMod DynamicMod::Conjunction(const DynamicMod& a, const DynamicMod& b) {
	/* 後の計算の都合上 a.value_m <= b.value_m としておく */
	if (a.value_m > b.value_m) {
		return Conjunction(b, a);
	}

	const uint64_t ma = a.mod_m;
	const uint64_t mb = b.mod_m;
	const uint64_t va = a.value_m;
	const uint64_t vb = b.value_m;

	const uint64_t gcd = GCD(ma, mb);
	const uint64_t lcm = ma / gcd * mb;
	const uint64_t diff = vb - va;

	if (diff % gcd != 0) {
		/* 例外ではなく mod_m == 0 のオブジェクトを返すなども考えている */
		throw std::runtime_error("no solution");
	}

	/* 方程式 ma * x - mb * y = gcd の解を求める */
	auto pair = Extended_GCD_unsigned(ma, mb);
	DynamicMod x(pair.first, mb / gcd);			// mod に注意

	/* 答えは va + ma * (diff / gcd) * x となる */
	x *= DynamicMod(diff / gcd, x.mod_m);
	return DynamicMod(va + ma * x.value_m, lcm);
}

DynamicMod DynamicMod::Conjunction(const std::vector<DynamicMod>& values) {
	DynamicMod product;
	for (const DynamicMod& value : values) {
		product = Conjunction(product, value);
	}
	return product;
}

/* bx = a の解を求める */
DynamicMod DynamicMod::Divide(const DynamicMod& a, const DynamicMod& b) {
	assert(Is_same_mod(a, b));
	
	const uint64_t va = a.value_m;
	const uint64_t vb = b.value_m;
	const uint64_t mod = a.mod_m;

	const uint64_t gcd = GCD(vb, mod);
	if (va % gcd != 0) {
		throw std::runtime_error("no solution");
	}
	
	auto pair = Extended_GCD_unsigned(vb, mod);
	DynamicMod ret(pair.first, mod / gcd);

	ret *= DynamicMod(va / gcd, ret.mod_m);
	return ret;
}

DynamicMod operator+(const DynamicMod& left, const DynamicMod& right) {
	DynamicMod ret(left);
	ret += right;
	return ret;
}

DynamicMod operator-(const DynamicMod& left, const DynamicMod& right) {
	DynamicMod ret(left);
	ret -= right;
	return ret;
}

DynamicMod operator*(const DynamicMod& left, const DynamicMod& right) {
	DynamicMod ret(left);
	ret *= right;
	return ret;
}

bool operator==(const DynamicMod& left, const DynamicMod& right) {
	return DynamicMod::Compare(left, right) == 0;
}

bool operator!=(const DynamicMod& left, const DynamicMod& right) {
	return DynamicMod::Compare(left, right) != 0;
}

bool operator<(const DynamicMod& left, const DynamicMod& right) {
	return DynamicMod::Compare(left, right) < 0;
}

bool operator<=(const DynamicMod& left, const DynamicMod& right) {
	return DynamicMod::Compare(left, right) <= 0;
}

bool operator>(const DynamicMod& left, const DynamicMod& right) {
	return DynamicMod::Compare(left, right) > 0;
}

bool operator>=(const DynamicMod& left, const DynamicMod& right) {
	return DynamicMod::Compare(left, right) >= 0;
}

#include <iostream>
using namespace std;
int main() {
	std::vector<DynamicMod> v;
	for (int i = 0; i < 3; ++i) {
		uint64_t a, b;
		cin >> a >> b;
		v.push_back(DynamicMod(a, b));
	}

	try {
		DynamicMod ans = DynamicMod::Conjunction(v);
		if (ans.Get_value() == 0) {
			uint64_t prod = 1;
			for (int i = 0; i < 3; ++i) {
				prod = LCM(prod, v[i].Get_mod());
			}
			cout << prod << endl;
		} else {
			cout << ans.Get_value() << endl;
		}
	} catch (...) {
		cout << -1 << endl;
	}
	return 0;
}