#192222 (C++14) No.551 夏休みの思い出（２）

• 問題: No.551 夏休みの思い出（２）
• ユーザー: anta
• 提出日時: 2017-07-28 23:30:10
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 312 ms / 4,000 ms
• コード長: 8,212 bytes
• コンパイル時間: 2,555 ms
• コンパイル使用メモリ: 193,664 KB
• 実行使用メモリ: 6,816 KB
• 最終ジャッジ日時: 2024-10-10 05:09:26
• 合計ジャッジ時間: 9,597 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	4 ms; 5,248 KB
testcase_03	AC	9 ms; 5,248 KB
testcase_04	AC	13 ms; 5,248 KB
testcase_05	AC	28 ms; 5,248 KB
testcase_06	AC	42 ms; 5,248 KB
testcase_07	AC	3 ms; 5,248 KB
testcase_08	AC	3 ms; 5,248 KB
testcase_09	AC	3 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	2 ms; 5,248 KB
testcase_12	AC	3 ms; 5,248 KB
testcase_13	AC	3 ms; 5,248 KB
testcase_14	AC	3 ms; 5,248 KB
testcase_15	AC	2 ms; 5,248 KB
testcase_16	AC	3 ms; 5,248 KB
testcase_17	AC	4 ms; 5,248 KB
testcase_18	AC	4 ms; 5,248 KB
testcase_19	AC	3 ms; 5,248 KB
testcase_20	AC	3 ms; 5,248 KB
testcase_21	AC	4 ms; 5,248 KB
testcase_22	AC	4 ms; 5,248 KB
testcase_23	AC	4 ms; 5,248 KB
testcase_24	AC	4 ms; 5,248 KB
testcase_25	AC	3 ms; 5,248 KB
testcase_26	AC	4 ms; 5,248 KB
testcase_27	AC	265 ms; 5,248 KB
testcase_28	AC	267 ms; 5,248 KB
testcase_29	AC	237 ms; 5,248 KB
testcase_30	AC	258 ms; 5,248 KB
testcase_31	AC	215 ms; 5,248 KB
testcase_32	AC	260 ms; 5,248 KB
testcase_33	AC	270 ms; 5,248 KB
testcase_34	AC	242 ms; 5,248 KB
testcase_35	AC	249 ms; 5,248 KB
testcase_36	AC	262 ms; 5,248 KB
testcase_37	AC	312 ms; 5,248 KB
testcase_38	AC	295 ms; 5,248 KB
testcase_39	AC	274 ms; 5,248 KB
testcase_40	AC	291 ms; 5,248 KB
testcase_41	AC	265 ms; 5,248 KB
testcase_42	AC	293 ms; 5,248 KB
testcase_43	AC	272 ms; 5,248 KB
testcase_44	AC	275 ms; 5,248 KB
testcase_45	AC	261 ms; 5,248 KB
testcase_46	AC	286 ms; 5,248 KB
testcase_47	AC	2 ms; 5,248 KB
testcase_48	AC	2 ms; 6,816 KB

ソースコード

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }


struct GModInt {
	static int Mod;
	unsigned x;
	GModInt() : x(0) { }
	GModInt(signed sig) { int sigt = sig % Mod; if (sigt < 0) sigt += Mod; x = sigt; }
	GModInt(signed long long sig) { int sigt = sig % Mod; if (sigt < 0) sigt += Mod; x = sigt; }
	int get() const { return (int)x; }

	GModInt &operator+=(GModInt that) { if ((x += that.x) >= (unsigned)Mod) x -= Mod; return *this; }
	GModInt &operator-=(GModInt that) { if ((x += Mod - that.x) >= (unsigned)Mod) x -= Mod; return *this; }
	GModInt &operator*=(GModInt that) { x = (unsigned long long)x * that.x % Mod; return *this; }
	GModInt &operator/=(GModInt that) { return *this *= that.inverse(); }

	GModInt operator+(GModInt that) const { return GModInt(*this) += that; }
	GModInt operator-(GModInt that) const { return GModInt(*this) -= that; }
	GModInt operator*(GModInt that) const { return GModInt(*this) *= that; }
	GModInt operator/(GModInt that) const { return GModInt(*this) /= that; }

	//Modと素であることが保証されるかどうか確認すること！
	GModInt inverse() const {
		signed a = x, b = Mod, u = 1, v = 0;
		while (b) {
			signed t = a / b;
			a -= t * b; std::swap(a, b);
			u -= t * v; std::swap(u, v);
		}
		if (u < 0) u += Mod;
		GModInt res; res.x = (unsigned)u;
		return res;
	}

	bool operator==(GModInt that) const { return x == that.x; }
	bool operator!=(GModInt that) const { return x != that.x; }
	GModInt operator-() const { GModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
int GModInt::Mod = 0;

typedef GModInt mint;
mint operator^(mint a, unsigned long long k) {
	mint r = 1;
	while (k) {
		if (k & 1) r *= a;
		a *= a;
		k >>= 1;
	}
	return r;
}

struct Polynomial {
	typedef mint Coef; typedef Coef Val;
	vector<Coef> coef;	//... + coef[2] x^2 + coef[1] x + coef[0]
	Polynomial() {}
	explicit Polynomial(int n) : coef(n) {}
	static Polynomial One() {
		Polynomial r(1);
		r.coef[0] = 1;
		return r;
	}
	static Polynomial X() {
		Polynomial r(2);
		r.coef[1] = 1;
		return r;
	}
	bool iszero() const { return coef.empty(); }
	int degree1() const { return coef.size(); }	//degree + 1
	int resize(int d) { if (degree1() < d) coef.resize(d); return d; }
	const Coef operator[](int i) const {
		return i >= degree1() ? Coef() : coef[i];
	}
	void canonicalize() {
		int i = coef.size();
		while (i > 0 && coef[i - 1] == Coef()) i --;
		coef.resize(i);
	}
	Val evalute(Val x) const {
		int d = degree1();
		Val t = 0, y = 1;
		rep(i, d) {
			t += y * coef[i];
			y *= x;
		}
		return t;
	}
	Polynomial &operator+=(const Polynomial &that) {
		int d = resize(that.degree1());
		for (int i = 0; i < d; i ++) coef[i] += that[i];
		canonicalize();
		return *this;
	}
	Polynomial operator+(const Polynomial &that) const { return Polynomial(*this) += that; }
	Polynomial &operator-=(const Polynomial &that) {
		int d = resize(that.degree1());
		for (int i = 0; i < d; i ++) coef[i] -= that[i];
		canonicalize();
		return *this;
	}
	Polynomial operator-(const Polynomial &that) const { return Polynomial(*this) -= that; }
	Polynomial operator-() const {
		int d = degree1();
		Polynomial res(d);
		for (int i = 0; i < d; i ++) res.coef[i] = - coef[i];
		return res;
	}
	//naive
	Polynomial operator*(const Polynomial &that) const {
		if (iszero() || that.iszero()) return Polynomial();
		int x = degree1(), y = that.degree1(), d = x + y - 1;
		Polynomial res(d);
		rep(i, x) rep(j, y)
			res.coef[i + j] += coef[i] * that.coef[j];
		res.canonicalize();
		return res;
	}
	//long division
	pair<Polynomial, Polynomial> divmod(const Polynomial &that) const {
		int x = degree1() - 1, y = that.degree1() - 1;
		int d = max(0, x - y);
		Polynomial q(d + 1), r = *this;
		for (int i = x; i >= y; i --) {
			Coef t = r.coef[i] / that.coef[y];
			q.coef[i - y] = t;
			assert(t * that.coef[y] == r.coef[i]);
			r.coef[i] = 0;
			if (t == 0) continue;
			for (int j = 0; j < y; j ++)
				r.coef[i - y + j] -= t * that.coef[j];
		}
		q.canonicalize(); r.canonicalize();
		return make_pair(q, r);
	}
	Polynomial operator/(const Polynomial &that) const { return divmod(that).first; }
	Polynomial operator%(const Polynomial &that) const { return divmod(that).second; }
	Polynomial divideByLC() const {
		if (degree1() == 0) return *this;
		Polynomial res(degree1());
		auto inv = coef[coef.size() - 1].inverse();
		rep(i, coef.size())
			res.coef[i] = coef[i] * inv;
		return res;
	}
};

Polynomial gcd(const Polynomial &x, const Polynomial &y) {
	if (y.iszero()) {
		return x.divideByLC();
	} else {
		return gcd(y, x % y);
	}
}

Polynomial powmod(Polynomial a, long long k, const Polynomial &mod) {
	Polynomial r = Polynomial::One();
	while (k != 0) {
		if (k & 1) r = r * a % mod;
		a = a * a % mod;
		k >>= 1;
	}
	return r;
}

struct RandomModInt {
	default_random_engine re;
	uniform_int_distribution<int> dist;
#ifndef _DEBUG
	RandomModInt() : re(random_device{}()), dist(1, mint::Mod - 1) { }
#else
	RandomModInt() : re(), dist(1, mint::Mod - 1) { }
#endif
	mint operator()() {
		mint r;
		r.x = dist(re);
		return r;
	}
};


Polynomial equalDegreeSplitting(const Polynomial &f, int d, RandomModInt &randomModInt) {
	int n = (int)f.degree1() - 1;
	assert(0 < d && d < n && n % d == 0);
	assert(f.coef[n].get() == 1);
	while (1) {
		Polynomial a;
		rep(i, n)
			a.coef.push_back(randomModInt());
		a.canonicalize();
		if (a.degree1() <= 1)
			continue;
		auto g1 = gcd(a, f);
		if (1 < g1.degree1())
			return g1;
		//b = a^((q^d-1)/2) mod f
		auto digit = powmod(a, (mint::Mod - 1) / 2, f);
		auto b = Polynomial::One();
		for (int i = 0; i < d; ++ i) {
			if(i != 0) b = powmod(b, mint::Mod, f);
			b = b * digit % f;
		}
		auto g2 = gcd(b - Polynomial::One(), f);
		if (1 < g2.degree1() && g2.degree1() < f.degree1())
			return g2;
	}
}

void equalDegreeFactorization(const Polynomial &f, int d, RandomModInt &randomModInt, vector<Polynomial> &factors) {
	int n = (int)f.degree1() - 1;
	if (n == d) {
		factors.push_back(f);
		return;
	}
	auto g = equalDegreeSplitting(f, d, randomModInt);
	equalDegreeFactorization(g, d, randomModInt, factors);
	equalDegreeFactorization(f / g, d, randomModInt, factors);
}

void polynomialFactorizationOverFiniteField(Polynomial f, RandomModInt &randomModInt, vector<pair<Polynomial, int>> &factors) {
	f.canonicalize();
	assert(0 < f.degree1() && f.coef[f.degree1() - 1].get() == 1);
	if (f.degree1() == 1) {
		factors.emplace_back(f, 1);
		return;
	}
	auto h = Polynomial::X();
	auto v = f;
	int i = 0;
	while (1 < v.degree1()) {
		++ i;
		h = powmod(h, mint::Mod, f);
		auto g = gcd(h - Polynomial::X(), v);
		if (1 < g.degree1()) {
			vector<Polynomial> ts;
			equalDegreeFactorization(g, i, randomModInt, ts);
			for (auto &&t : ts) {
				int e = 0;
				do {
					++ e;
					v = v / t;
				} while ((v % t).iszero());
				factors.emplace_back(t, e);
			}
		}
	}
}

int main() {
	int P; int R;
	while (~scanf("%d%d", &P, &R)) {
		mint::Mod = P;
		RandomModInt randomModInt;
		int Q;
		scanf("%d", &Q);
		rep(ii, Q) {
			int A; int B; int C;
			scanf("%d%d%d", &A, &B, &C);
			Polynomial poly(3);
			auto inv = mint(A).inverse();
			poly.coef[0] = inv * C;
			poly.coef[1] = inv * B;
			poly.coef[2] = 1;
			vector<pair<Polynomial, int>> factors;
			polynomialFactorizationOverFiniteField(poly, randomModInt, factors);
			vector<int> ans;
			for (auto &&t : factors) {
				if (t.first.degree1() == 2)
					ans.push_back((mint() - t.first.coef[0]).get());
			}
			sort(ans.begin(), ans.end());
			if (ans.empty()) {
				puts("-1");
			} else {
				for (int i = 0; i < (int)ans.size(); ++ i) {
					if (i != 0) putchar(' ');
					printf("%d", ans[i]);
				}
				puts("");
			}
		}
	}
	return 0;
}