結果
| 問題 |
No.303 割れません
|
| ユーザー |
 Yang33
|
| 提出日時 | 2018-09-29 23:10:52 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,766 bytes |
| コンパイル時間 | 2,320 ms |
| コンパイル使用メモリ | 189,900 KB |
| 実行使用メモリ | 10,752 KB |
| 最終ジャッジ日時 | 2024-10-12 08:52:28 |
| 合計ジャッジ時間 | 13,909 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | TLE * 1 -- * 13 |
ソースコード
#include "bits/stdc++.h"
using namespace std;
using VS = vector<string>; using LL = long long;
using VI = vector<int>; using VVI = vector<VI>;
using PII = pair<int, int>; using PLL = pair<LL, LL>;
using VL = vector<LL>; using VVL = vector<VL>;
#define ALL(a) begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9; const LL LINF = 1e16;
const LL MOD = 1000000007; const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 }; int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
/* ----- 2018/09/29 Problem: yukicoder 303 / Link: http://yukicoder.me/problems/no/303 ----- */
/* ------問題------
-----問題ここまで----- */
/* -----解説等-----
----解説ここまで---- */
struct BigInt {
public:
using LL = long long int;
static const LL BASE = 1000000000;
const int DIG = 9;
bool neg;
std::vector<LL> dig;
BigInt() : neg(false), dig(1, 0ll) {}
BigInt(const char* str) : BigInt(std::string(str)) {}
BigInt(const std::string& str) : neg(false) {
if (str.empty()) {
dig.assign(1, 0);
return;
}
int b = 0;
if (str[b] == '-') {
neg = true;
++b;
}
LL crt = 0;
LL p = 1;
for (int i = (int)(str.size()) - 1; i >= b; --i, p *= 10) {
if (p == BASE) {
dig.emplace_back(crt);
crt = 0;
p = 1;
}
if (!isdigit(str[i])) {
throw "Non digit is given.";
}
crt += p * (str[i] - '0');
}
dig.emplace_back(crt);
norm();
}
BigInt(LL x) : neg(x < 0), dig(1, std::abs(x)) {
for (unsigned int i = 0; i < dig.size(); ++i) {
if (dig[i] >= BASE) {
dig.emplace_back(dig[i] / BASE);
dig[i] %= BASE;
}
}
}
BigInt& operator=(const BigInt& rhs) {
neg = rhs.neg;
dig = rhs.dig;
return *this;
}
BigInt& operator=(LL x) { return *this = BigInt(x); }
BigInt& operator=(const char* s) { return *this = BigInt(s); }
BigInt& operator=(const std::string& s) { return *this = BigInt(s); }
bool iszero() const {
return dig.size() == 1 && dig[0] == 0;
}
BigInt operator-() const {
BigInt res = *this;
if (!res.iszero())
res.neg = !res.neg;
return res;
}
//! ignoring sign
static int comp(const BigInt& l, const BigInt& r) {
if (l.dig.size() != r.dig.size())
return (l.dig.size() < r.dig.size() ? -1 : 1);
for (int i = (int)(l.dig.size()) - 1; i >= 0; --i) {
if (l.dig[i] != r.dig[i])
return (l.dig[i] < r.dig[i] ? -1 : 1);
}
return 0;
}
//! add ignoring sign
static void add(BigInt& l, const BigInt& rhs) {
unsigned int i;
for (i = 0; i < rhs.dig.size(); ++i) {
if (l.dig.size() <= i) {
l.dig.emplace_back(rhs.dig[i]);
}
else {
l.dig[i] += rhs.dig[i];
if (l.dig[i] >= BASE) {
l.dig[i] -= BASE;
if (l.dig.size() <= i + 1)
l.dig.emplace_back(0);
l.dig[i + 1]++;
}
else if (l.dig[i] < 0) {
l.dig[i] += BASE;
if (l.dig.size() <= i + 1)
l.dig.emplace_back(0);
l.dig[i + 1]--;
}
}
}
for (; i < l.dig.size(); ++i)
if (l.dig[i] >= BASE) {
l.dig[i] -= BASE;
if (l.dig.size() <= i + 1)
l.dig.emplace_back(0);
l.dig[i + 1]++;
}
}
// subtract ignoring sign, supposed to l >= rhs
static void sub(BigInt& l, const BigInt& rhs) {
unsigned int i;
for (i = 0; i < rhs.dig.size(); ++i) {
l.dig[i] -= rhs.dig[i];
if (l.dig[i] < 0) {
l.dig[i] += BASE;
l.dig[i + 1]--;
}
}
for (; i < l.dig.size(); ++i)
if (l.dig[i] < 0) {
l.dig[i] += BASE;
l.dig[i + 1]--;
}
}
void flip() {
for (unsigned int i = 0; i < dig.size(); ++i)
dig[i] *= -1;
}
void norm() {
while (dig.size() > 1 && dig.back() == 0) dig.pop_back();
if (iszero()) neg = false;
}
bool operator==(const BigInt& rhs) const {
if (neg != rhs.neg || dig.size() != rhs.dig.size()) return false;
return comp(*this, rhs) == 0;
}
bool operator<(const BigInt& rhs) const {
if (neg != rhs.neg) return neg ? true : false;
if (neg) return comp(rhs, *this) == -1;
return comp(*this, rhs) == -1;
}
bool operator<=(const BigInt& rhs) const {
if (neg != rhs.neg) return neg ? true : false;
if (neg) return comp(rhs, *this) <= 0;
return comp(*this, rhs) <= 0;
}
bool operator!=(const BigInt& rhs) const { return !(*this == rhs); }
bool operator>(const BigInt& rhs) const { return rhs < *this; }
bool operator>=(const BigInt& rhs) const { return rhs <= *this; }
// ignoring sign
void incl() {
for (unsigned int i = 0; i < dig.size(); ++i)
if (++dig[i] == BASE) {
dig[i] = 0;
if (i + 1 == dig.size()) {
dig.push_back(1);
break;
}
}
else break;
}
// ignoring sign
void decl() {
if (iszero()) {
dig[0] = 1;
neg = true;
return;
}
for (unsigned int i = 0; i < dig.size(); ++i)
if (--dig[i] == -1)
dig[i] = BASE - 1;
else break;
norm();
}
BigInt& operator++() {
if (!neg) incl(); else decl();
return *this;
}
BigInt operator++(int) {
BigInt res = *this;
if (!neg) incl(); else decl();
return res;
}
BigInt& operator--() {
if (!neg) decl(); else incl();
return *this;
}
BigInt operator--(int) {
BigInt res = *this;
if (!neg) decl(); else incl();
return res;
}
BigInt& operator+=(const BigInt& rhs) {
if (!this->neg) {
if (!rhs.neg)
add(*this, rhs);
else {
if (comp(*this, rhs) >= 0)
sub(*this, rhs);
else {
flip();
add(*this, rhs);
neg = true;
}
}
}
else {
if (!rhs.neg) {
if (comp(rhs, *this) >= 0) {
flip();
add(*this, rhs);
neg = false;
}
else
sub(*this, rhs);
}
else
add(*this, rhs);
}
norm();
return *this;
}
BigInt& operator-=(const BigInt& rhs) { return *this += -rhs; }
BigInt operator+(const BigInt& rhs) const { BigInt res = *this; return res += rhs; }
BigInt operator-(const BigInt& rhs) const { BigInt res = *this; return res -= rhs; }
BigInt operator*(const BigInt& rhs) const {
BigInt res;
res.dig.assign(dig.size() + rhs.dig.size() + 1, 0ll);
res.neg = neg ^ rhs.neg;
for (unsigned i = 0; i < rhs.dig.size(); ++i) {
if (rhs.dig[i] == 0) continue;
for (unsigned j = 0; j < dig.size(); ++j) {
res.dig[i + j] += rhs.dig[i] * dig[j];
if (res.dig[i + j] >= BASE) {
res.dig[i + j + 1] += res.dig[i + j] / BASE;
res.dig[i + j] %= BASE;
}
}
}
res.norm();
return res;
}
BigInt operator*=(const BigInt& rhs) { return *this = *this * rhs; }
static void divll(BigInt& x, LL& r, LL d) {
bool lneg = x.neg;
x.neg ^= (d < 0);
if (d < 0) d *= -1;
r = 0;
for (int i = (int)x.dig.size() - 1; i >= 0; --i) {
r = r * BASE + x.dig[i];
x.dig[i] = r / d;
r %= d;
}
x.norm();
if (r != 0 && lneg)
r *= -1;
}
void powB(LL x) {
if (iszero()) return;
while (x > 0) {
dig.insert(dig.begin(), 0ll);
--x;
}
}
static void divmod(BigInt& q, BigInt& r, const BigInt& lhs, const BigInt& rhs) {
int cmp = comp(lhs, rhs);
if (cmp < 0) {
q.dig = std::vector<LL>(1, 0ll);
q.neg = false;
r = lhs;
return;
}
else if (cmp == 0) {
q.dig = std::vector<LL>(1, 1ll);
q.neg = false;
r.dig = std::vector<LL>(1, 0ll);
r.neg = false;
return;
}
if (rhs.dig.size() == 1) {
LL rl;
q = lhs;
divll(q, rl, rhs.dig[0] * (rhs.neg ? -1ll : 1ll));
r = rl;
return;
}
q.neg = r.neg = false;
int u = lhs.dig.size() - rhs.dig.size() + 1;
q.dig.assign(u + 1, 0ll);
LL K = BASE / (rhs.dig.back() + 1);
BigInt ltmp = lhs, rtmp = rhs;
ltmp.neg = rtmp.neg = false;
if (K > 1) {
ltmp *= K;
rtmp *= K;
}
LL x = ltmp.dig.back() / rtmp.dig.back();
if (x == 0) {
--u;
x = (ltmp.dig.back() * BASE + ltmp.dig[ltmp.dig.size() - 2]) / rtmp.dig.back();
}
BigInt w = 0ll;
while (true) {
w = rtmp;
w.powB(u);
if (comp(w, ltmp) > 0) {
--u;
continue;
}
while (true) {
w = rtmp * x;
w.powB(u);
if (comp(w, ltmp) <= 0) break;
--x;
}
q.dig[u--] = x;
ltmp -= w;
if (ltmp == 0ll || u < 0) break;
x = std::min(BASE - 1,
(ltmp.dig.back() * BASE + ltmp.dig[ltmp.dig.size() - 2]) / rtmp.dig.back());
}
q.norm();
r = ltmp;
if (ltmp != 0ll) divll(r, x, K);
q.neg = lhs.neg ^ rhs.neg;
r.neg = lhs.neg;
r.norm();
}
BigInt operator/(const BigInt& rhs) const {
BigInt q, r;
divmod(q, r, *this, rhs);
return q;
}
BigInt operator%(const BigInt& rhs) const {
BigInt q, r;
divmod(q, r, *this, rhs);
return r;
}
BigInt& operator/=(BigInt rhs) { return *this = *this / rhs; }
BigInt& operator%=(BigInt rhs) { return *this = *this % rhs; }
std::string to_string() const {
//assert(!dig.empty());
std::string res = neg ? "-" : "";
std::ostringstream os;
os << std::to_string(dig.back());
for (int i = (int)(dig.size()) - 2; i >= 0; --i) {
os << std::setfill('0') << std::setw(DIG) << dig[i];
}
res += os.str();
return res;
}
// convert long long int anyway
LL to_ll() const {
LL res = 0, p = 1;
for (unsigned int i = 0; i < dig.size(); ++i) {
res += dig[i] * p;
p *= BASE;
}
return res * (neg ? -1ll : 1);
}
};
int xx = 0;
BigInt zero(xx);
std::ostream& operator<<(std::ostream& os, const BigInt& x) { return os << x.to_string(); }
std::istream& operator>>(std::istream& is, BigInt& x) { string s; is >> s; x = s; return is; }
//a*B
template<typename T>
vector<vector<T>> mul(vector<vector<T>> &A, vector<vector<T>> &B) {
vector<vector<T>> C(A.size(), vector<T>(B[0].size()));
FOR(i, 0, (int)A.size()) {
FOR(k, 0, (int)B.size()) {
if (!A[i][k].iszero()) {
FOR(j, 0, (int)B[0].size()) {
if(!B[k][j].iszero())C[i][j] = (C[i][j] + (A[i][k]) * (B[k][j]));
}
}
}
}
return C;
}
//a^N べき乗法 logN
template<typename T>
vector<vector<T>> pow(vector<vector<T>> A, long long n) {
vector<vector<T>> B((int)A.size(), vector<T>((int)A.size()));
FOR(i, 0, (int)A.size()) {
B[i][i] = 1;
}
while (n > 0) {
if (n & 1) B = mul(B, A);
A = mul(A, A);
n >>= 1;
}
return B;
}
BigInt fib(LL n) {
n--;
vector<vector<BigInt>>mat(2, vector<BigInt>(2, 1));
mat[1][1] = zero;
mat = pow<BigInt>(mat, n);
return mat[0][0];
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
LL N; cin >> N;
if (N == 2) {
cout << 3 << endl;
cout << "INF" << endl;
}
else {
cout << N << endl;
if (N & 1) {
cout << fib(N) << endl;
}
else {
auto divfib = fib(N / 2);
cout << fib(N) - divfib * divfib << endl;
}
}
return 0;
}