結果
| 問題 |
No.550 夏休みの思い出（１）
|
| コンテスト | |
| ユーザー |
 anta
|
| 提出日時 | 2017-07-28 23:31:43 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 8,170 bytes |
| コンパイル時間 | 2,590 ms |
| コンパイル使用メモリ | 195,864 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-11 05:32:45 |
| 合計ジャッジ時間 | 3,959 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 55 |
ソースコード
#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() {
long long A; long long B; long long C;
while (~scanf("%lld%lld%lld", &A, &B, &C)) {
mint::Mod = 2000000011;
RandomModInt randomModInt;
Polynomial poly(4);
poly.coef[0] = C;
poly.coef[1] = B;
poly.coef[2] = A;
poly.coef[3] = 1;
vector<pair<Polynomial, int>> factors;
polynomialFactorizationOverFiniteField(poly, randomModInt, factors);
vector<int> ans;
for (auto &&t : factors) {
if (t.first.degree1() == 2) {
int x = (mint() - t.first.coef[0]).get();
ans.push_back(x < mint::Mod / 2 ? x : -(mint::Mod - x));
}
}
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;
}