結果
| 問題 | No.3056 量子コンピュータで素因数分解 Easy |
| ユーザー |
👑  emthrm
|
| 提出日時 | 2020-02-05 03:29:20 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,817 bytes |
| コンパイル時間 | 3,591 ms |
| コンパイル使用メモリ | 228,732 KB |
| 実行使用メモリ | 53,560 KB |
| 平均クエリ数 | 0.27 |
| 最終ジャッジ日時 | 2024-06-10 07:15:30 |
| 合計ジャッジ時間 | 8,231 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | TLE | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
ソースコード
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
template <typename T> using posteriority_queue = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
template <typename T> void unique(vector<T> &a) { a.erase(unique(ALL(a)), a.end()); }
struct IOSetup {
IOSetup() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(20);
}
} iosetup;
// "base" must be a power of 10.
const int lg10_base = 9, base = static_cast<int>(round(pow(10, lg10_base)));
struct BigInt {
int sign; vector<int> dat;
BigInt(ll val = 0) { *this = val; }
BigInt(const string &s) { *this = s; }
vector<ll> convert_base(int new_lg10_base, ll new_base) const {
// assert(new_base == static_cast<int>(round(pow(10, new_lg10_base))))
int mx_base = max(lg10_base, new_lg10_base);
vector<ll> p(mx_base + 1, 1);
FOR(i, 1, mx_base + 1) p[i] = p[i - 1] * 10;
vector<ll> res;
ll now_val = 0;
int now_lg10_base = 0;
for (int e : dat) {
now_val += p[now_lg10_base] * e;
now_lg10_base += lg10_base;
while (now_lg10_base >= new_lg10_base) {
res.emplace_back(now_val % new_base);
now_val /= new_base;
now_lg10_base -= new_lg10_base;
}
}
res.emplace_back(now_val);
while (!res.empty() && res.back() == 0) res.pop_back();
return res;
}
int digit_sum() {
assert(sign == 1);
string s = to_string();
int res = 0;
for (char c : s) res += c - '0';
return res;
}
int length() {
if (dat.empty()) return 1;
int res = lg10_base * (dat.size() - 1);
int tmp = dat.back();
while (tmp > 0) { ++res; tmp /= 10; }
return res;
}
BigInt pow(BigInt exponent) {
BigInt res = 1, tmp = *this;
while (exponent > 0) {
if (exponent.dat[0] & 1) res *= tmp;
tmp *= tmp;
exponent /= 2;
}
return res;
}
ll to_llong() const {
assert(*this >= LLONG_MIN && *this <= LLONG_MAX);
ll res = 0;
for (int i = static_cast<int>(dat.size()) - 1; i >= 0; --i) (res *= base) += dat[i];
return res;
}
string to_string() { stringstream ss; ss << *this; string res; ss >> res; return res; }
void trim() {
while (!dat.empty() && dat.back() == 0) dat.pop_back();
if (dat.empty()) sign = 1;
}
BigInt &operator=(ll val) {
sign = 1;
if (val < 0) { sign = -1; val *= -1;}
dat.clear();
for (; val > 0; val /= base) dat.emplace_back(val % base);
return *this;
}
BigInt &operator=(const string &s) {
sign = 1;
dat.clear();
if (!s.empty()) {
int tail = 0;
if (s[tail] == '-' || s[tail] == '+') {
if (s[tail] == '-') sign = -1;
++tail;
}
for (int i = s.length() - 1; i >= tail; i -= lg10_base) {
int val = 0;
for (int j = max(tail, i - lg10_base + 1); j <= i; ++j) val = val * 10 + (s[j] - '0');
dat.emplace_back(val);
}
}
trim();
return *this;
}
BigInt &operator=(const BigInt &x) {
sign = x.sign;
dat.resize(x.dat.size());
copy(ALL(x.dat), dat.begin());
return *this;
}
BigInt &operator+=(const BigInt &x) {
if (sign == x.sign) {
bool carry = false;
for (int i = 0; i < max(dat.size(), x.dat.size()) || carry; ++i) {
if (i == dat.size()) dat.emplace_back(0);
dat[i] += (i < x.dat.size() ? x.dat[i] : 0) + carry;
carry = dat[i] >= base;
if (carry) dat[i] -= base;
}
} else {
*this -= -x;
}
return *this;
}
BigInt &operator-=(const BigInt &x) {
if (sign == x.sign) {
BigInt abs_this = *this, abs_x = x;
abs_this.sign = 1; abs_x.sign = 1;
if (abs_this >= abs_x) {
bool carry = false;
for (int i = 0; i < dat.size() || carry; ++i) {
dat[i] -= (i < x.dat.size() ? x.dat[i] : 0) + carry;
carry = dat[i] < 0;
if (carry) dat[i] += base;
}
trim();
} else {
*this = -(x - *this);
}
} else {
*this += -x;
}
return *this;
}
BigInt &operator*=(const BigInt &x) {
const int new_log10_base = 6, new_base = 1000000;
vector<ll> this6 = convert_base(new_log10_base, new_base), x6 = x.convert_base(new_log10_base, new_base);
vector<ll> res = karatsuba(this6, 0, this6.size(), x6, 0, x6.size());
REP(i, res.size()) {
ll quo = res[i] / new_base;
if (quo > 0) {
if (i + 1 == res.size()) res.emplace_back(0);
res[i + 1] += quo;
}
res[i] %= new_base;
}
string s = (sign * x.sign == 1 ? "+" : "-");
for (int i = static_cast<int>(res.size()) - 1; i >= 0; --i) {
string tmp = std::to_string(res[i]);
REP(_, new_log10_base - tmp.size()) s += '0';
s += tmp;
}
return *this = s;
}
BigInt &operator/=(int x) { return *this = divide(x).first; }
BigInt &operator/=(const BigInt &x) { return *this = divide(x).first; }
BigInt &operator%=(int x) { return *this = divide(x).second; }
BigInt &operator%=(const BigInt &x) { return *this = divide(x).second; }
bool operator==(const BigInt &x) const {
if (sign != x.sign || dat.size() != x.dat.size()) return false;
int sz = dat.size();
REP(i, sz) if (dat[i] != x.dat[i]) return false;
return true;
}
bool operator!=(const BigInt &x) const { return !(*this == x); }
bool operator<(const BigInt &x) const {
if (sign != x.sign) return sign < x.sign;
if (dat.size() != x.dat.size()) return sign * dat.size() < x.sign * x.dat.size();
for (int i = static_cast<int>(dat.size()) - 1; i >= 0; --i) {
if (dat[i] != x.dat[i]) return dat[i] * sign < x.dat[i] * x.sign;
}
return false;
}
bool operator<=(const BigInt &x) const { return !(x < *this); }
bool operator>(const BigInt &x) const { return x < *this; }
bool operator>=(const BigInt &x) const { return !(*this < x); }
BigInt &operator++() { return *this += 1; }
BigInt operator++(int) { BigInt res = *this; ++*this; return res; }
BigInt &operator--() { return *this -= 1; }
BigInt operator--(int) { BigInt res = *this; --*this; return res; }
BigInt operator+() const { return *this; }
BigInt operator-() const { BigInt res = *this; res.sign *= -1; return res; }
BigInt operator+(const BigInt &x) const { return BigInt(*this) += x; }
BigInt operator-(const BigInt &x) const { return BigInt(*this) -= x; }
BigInt operator*(const BigInt &x) const { return BigInt(*this) *= x; }
BigInt operator/(int x) const { return BigInt(*this) /= x; }
BigInt operator/(const BigInt &x) const { return BigInt(*this) /= x; }
BigInt operator%(int x) const { return BigInt(*this) %= x; }
BigInt operator%(const BigInt &x) const { return BigInt(*this) %= x; }
friend ostream &operator<<(ostream &os, const BigInt &x) {
if (x.sign == -1) os << '-';
os << (x.dat.empty() ? 0 : x.dat.back());
for (int i = static_cast<int>(x.dat.size()) - 2; i >= 0; --i) os << setw(lg10_base) << setfill('0') << x.dat[i];
return os;
}
friend istream &operator>>(istream &is, BigInt &x) { string s; is >> s; x = s; return is; }
private:
vector<ll> karatsuba(vector<ll> &a, int a_l, int a_r, vector<ll> &b, int b_l, int b_r) {
int a_len = a_r - a_l, b_len = b_r - b_l;
if (a_len < b_len) return karatsuba(b, b_l, b_r, a, a_l, a_r);
vector<ll> res(a_len + b_len, 0);
if (b_len <= 32) {
FOR(i, a_l, a_r) FOR(j, b_l, b_r) res[(i - a_l) + (j - b_l)] += a[i] * b[j];
} else {
int mid = (a_len + 1) / 2, n = min(a_len, mid);
for (int i = a_l; i + mid < a_r; ++i) a[i] += a[i + mid];
for (int i = b_l; i + mid < b_r; ++i) b[i] += b[i + mid];
vector<ll> tmp = karatsuba(a, a_l, a_l + mid, b, b_l, b_l + n);
REP(i, tmp.size()) res[mid + i] = tmp[i];
for (int i = a_l; i + mid < a_r; ++i) a[i] -= a[i + mid];
for (int i = b_l; i + mid < b_r; ++i) b[i] -= b[i + mid];
tmp = karatsuba(a, a_l, a_l + mid, b, b_l, b_l + n);
REP(i, tmp.size()) { res[i] += tmp[i]; res[mid + i] -= tmp[i]; }
tmp = karatsuba(a, a_l + mid, a_r, b, b_l + n, b_r);
REP(i, tmp.size()) { res[mid + i] -= tmp[i]; res[(mid << 1) + i] += tmp[i]; }
}
while (!res.empty() && res.back() == 0) res.pop_back();
return res;
}
pair<BigInt, int> divide(int x) {
// assert(!x.dat.empty());
BigInt dividend = *this;
if (x < 0) { dividend.sign *= -1; x *= -1; }
ll rem = 0;
for (int i = static_cast<int>(dividend.dat.size()) - 1; i >= 0; --i) {
ll tmp = rem * base + dividend.dat[i];
dividend.dat[i] = static_cast<int>(tmp / x);
rem = tmp % x;
}
dividend.trim();
return {dividend, static_cast<int>(rem)};
}
pair<BigInt, BigInt> divide(const BigInt &x) {
// assert(!x.dat.empty());
int k = base / (x.dat.back() + 1);
BigInt dividend = *this, divisor = x;
dividend.sign = 1; divisor.sign = 1;
dividend *= k; divisor *= k;
BigInt quo, rem = 0;
quo.dat.resize(dividend.dat.size());
int sz = divisor.dat.size();
for (int i = static_cast<int>(dividend.dat.size()) - 1; i >= 0; --i) {
rem.dat.insert(rem.dat.begin(), dividend.dat[i]);
quo.dat[i] = static_cast<int>(((sz < rem.dat.size() ? 1LL * rem.dat[sz] * base : 0) + (sz - 1 < rem.dat.size() ? rem.dat[sz - 1] : 0)) / divisor.dat.back());
rem -= divisor * quo.dat[i];
while (rem.sign == -1) { rem += divisor; --quo.dat[i]; }
}
quo.sign = sign * x.sign; rem.sign = sign;
quo.trim(); rem.trim();
return {quo, rem / k};
}
};
BigInt __gcd(BigInt a, BigInt b) { while (!b.dat.empty()) swap(a %= b, b); return a; }
BigInt __lcm(const BigInt &a, const BigInt &b) { return a / __gcd(a, b) * b; }
BigInt abs(const BigInt &x) { BigInt res = x; res.sign = 1; return res; }
BigInt max(const BigInt &a, const BigInt &b) { return a < b ? b : a; }
BigInt min(const BigInt &a, const BigInt &b) { return a < b ? a : b; }
// https://speakerdeck.com/gyudon/shorfalsearugorizumu
int main() {
BigInt n; cin >> n;
cout << "? 2" << endl;
BigInt r; cin >> r;
assert(r % 2 == 0);
BigInt p = BigInt(2).pow(r / 2);
p += (__gcd(n, p + 1) == 1 ? -1 : 1);
cout << "! " << p << ' ' << n / p << endl;
return 0;
}