結果
| 問題 |
No.303 割れません
|
| ユーザー |
 square1001
|
| 提出日時 | 2018-05-26 22:40:34 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,575 bytes |
| コンパイル時間 | 1,157 ms |
| コンパイル使用メモリ | 87,048 KB |
| 実行使用メモリ | 145,856 KB |
| 最終ジャッジ日時 | 2024-06-28 18:17:21 |
| 合計ジャッジ時間 | 12,707 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | TLE * 1 -- * 13 |
ソースコード
#ifndef ___CLASS_BIGINT
#define ___CLASS_BIGINT
// +----------------------------------
// | BigInteger Library Version 2.0
// | Author: square1001 (+ E869120)
// | Date: July 24th, 2016
// | Last Revision: May 24th, 2018
// | Language: C++11 / C++14
// +---------------------------------
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
class unsigned128 {
private:
uint64_t x0, x1;
static constexpr uint32_t maxval = 4294967295u;
public:
unsigned128() : x0(0), x1(0) {};
unsigned128(uint64_t n_) : x0(n_), x1(0) {};
unsigned128& operator=(const uint64_t x) { x0 = x, x1 = 0; return *this; }
unsigned128& operator+=(const unsigned128& x) { x0 += x.x0; x1 += x.x1 + (x0 >= x.x0 ? 0 : 1); return *this; }
unsigned128& operator-=(const unsigned128& x) { x0 -= x.x0; x1 -= x.x1 + (x0 <= x0 + x.x0 ? 0 : 1); return *this; }
unsigned128& operator*=(const unsigned128& x) {
uint64_t xl = (x0 & maxval) * (x.x0 >> 32), xr = (x0 >> 32) * (x.x0 & maxval), xs = ((xl + xr) & maxval) << 32;
x1 = x0 * x.x1 + x1 * x.x0 + (x0 >> 32) * (x.x0 >> 32) + ((xl + xr) >> 32) + (xl + xr >= xl ? 0 : 1ull << 32) + (xs + (x0 & maxval) * (x.x0 & maxval) >= xs ? 0 : 1);
x0 *= x.x0;
return *this;
}
unsigned128& operator<<=(const unsigned x) {
x1 = (x < 64 ? (x1 << x) + (x == 0 ? 0 : x0 >> (64 - x)) : x0 << (x - 64));
x0 = (x < 64 ? x0 << x : 0);
return *this;
}
unsigned128& operator>>=(const unsigned x) {
x0 = (x < 64 ? (x0 >> x) + (x == 0 ? 0 : x1 << (64 - x)) : x1 >> (x - 64));
x1 = (x < 64 ? x1 >> x : 0);
return *this;
}
unsigned128 operator+(const unsigned128& x) const { return unsigned128(*this) += x; }
unsigned128 operator-(const unsigned128& x) const { return unsigned128(*this) -= x; }
unsigned128 operator*(const unsigned128& x) const { return unsigned128(*this) *= x; }
unsigned128 operator<<(const unsigned x) const { return unsigned128(*this) <<= x; }
unsigned128 operator >> (const unsigned x) const { return unsigned128(*this) >>= x; }
uint64_t get64() const { return x0; }
uint32_t get32() const { return x0 & 4294967295u; }
};
template <uint32_t mod> class modint {
// Assertion: mod < 2^31
private:
uint32_t n;
static const int shifts = 62;
static const uint64_t multiplier = (1ull << shifts) / mod;
public:
modint() : n(0) {};
modint(uint32_t n_) : n(n_) {};
modint& operator=(const uint32_t x) { n = x; return *this; }
modint& operator+=(const modint& x) { n = (n + x.n < mod ? n + x.n : n + x.n - mod); return *this; }
modint& operator-=(const modint& x) { n = (mod + n - x.n < mod ? mod + n - x.n : n - x.n); return *this; }
modint& operator*=(const modint& x) {
uint64_t w = 1ull * n * x.n;
w -= ((unsigned128(w) * multiplier) >> shifts).get64() * mod;
n = (w < mod ? w : w - mod);
return *this;
}
modint operator+(const modint& x) const { return modint(*this) += x; }
modint operator-(const modint& x) const { return modint(*this) -= x; }
modint operator*(const modint& x) const { return modint(*this) *= x; }
int get() const { return n; }
};
class bigint {
private:
int size_;
std::vector<int> arr;
void resize(int target) {
size_ = target;
arr.resize(size_);
}
public:
static const int maxdigit = 5; // maxdigit <= 5
static const int maxvalue = 100000; // maxvalue = 10^maxdigit
bigint() : size_(1), arr(std::vector<int>({ 0 })) {};
bigint(const std::string& s) {
size_ = 1;
while (size_ < (s.size() + maxdigit - 1) / maxdigit) size_ <<= 1;
arr = std::vector<int>(size_, 0);
for (int i = s.size() - 1; i >= 0; --i) {
arr[i / maxdigit] = arr[i / maxdigit] * 10 + (s[s.size() - i - 1] - '0');
}
}
bigint(long long x) {
(*this) = x;
}
bigint(const bigint& x) {
(*this) = x;
}
int size() const {
return size_;
}
int digit() const {
for (int i = size_ - 1; i >= 0; --i) {
if (arr[i] != 0) continue;
int mul = 1;
for (int j = 0; j < maxdigit; ++j) {
mul *= 10;
if (arr[j] < mul) return maxdigit * i + j;
}
}
return 1; // exception to val = 0
}
std::string to_string() const {
std::string ret(size_ * maxdigit, '-');
int mx = 0;
for (int i = 0; i < size_; ++i) {
int x = arr[i];
for (int j = 0; j < maxdigit; ++j) {
if (x % 10 != 0) mx = i * maxdigit + j;
ret[size_ * maxdigit - i * maxdigit - j - 1] = x % 10 + '0';
x /= 10;
}
}
return ret.substr(size_ * maxdigit - mx - 1);
}
bigint& operator=(const long long x) {
long long subx = x;
int usesize = 0;
while (subx > 0) subx /= maxvalue, usesize++;
size_ = 1;
while (size_ < usesize) size_ <<= 1;
arr = std::vector<int>(size_, 0);
subx = x;
for (int i = 0; i < size_; ++i) {
arr[i] = subx % maxvalue;
subx /= maxvalue;
}
return *this;
}
bigint& operator+=(const bigint& x) {
// Time complexity: linear
if (x.size_ > size_) resize(x.size_);
int carry = 0;
for (int i = 0; i < x.size_; ++i) {
if ((arr[i] += x.arr[i] + carry) >= maxvalue) arr[i] -= maxvalue, carry = 1;
else carry = 0;
}
if (carry == 1) resize(size_ << 1), arr[size_ >> 1] = 1;
return *this;
}
bigint& operator-=(const bigint& x) {
// Time complexity: linear
// Assertion: this >= x. Runtime error's possible if this < x
int carry = 0, mx = 1;
for (int i = 0; i < size_; ++i) {
if ((arr[i] -= (i < x.size_ ? x.arr[i] : 0) + carry) < 0) arr[i] += maxvalue, carry = 1;
while (arr[i] != 0 && mx < i + 1) mx *= 2;
}
if (mx != size_) resize(mx);
return *this;
}
bigint& operator*=(const bigint& x) {
// Time complexity: linearithmic
// Assertion: mod1 <= mod2
const unsigned mod1 = 1811939329, root1 = 3;
const unsigned mod2 = 2013265921, root2 = 3;
int magic = binpow(mod1, mod2 - 2, mod2);
resize(std::max(size_, x.size_) * 2);
std::vector<modint<mod1> > a1(size_), x1(size_);
std::vector<modint<mod2> > a2(size_), x2(size_);
for (int i = 0; i < size_; ++i) a1[i] = arr[i], a2[i] = arr[i];
for (int i = 0; i < x.size_; ++i) x1[i] = x.arr[i], x2[i] = x.arr[i];
fourier_transform(size_, a1, root1, false);
fourier_transform(size_, a2, root2, false);
fourier_transform(size_, x1, root1, false);
fourier_transform(size_, x2, root2, false);
for (int i = 0; i < size_; ++i) a1[i] *= x1[i], a2[i] *= x2[i];
fourier_transform(size_, a1, root1, true);
fourier_transform(size_, a2, root2, true);
long long carry = 0; int mx = 1;
for (int i = 0; i < size_; ++i) {
long long val = 1LL * (a2[i].get() - a1[i].get() + mod2) * magic % mod2 * mod1 + a1[i].get();
arr[i] = (val + carry) % maxvalue;
carry = (val + carry) / maxvalue;
while (arr[i] != 0 && mx < i + 1) mx *= 2;
}
if (mx != size_) resize(mx);
return *this;
}
friend bool operator<(const bigint& x1, const bigint& x2) {
if (x1.size_ != x2.size_) return x1.size_ < x2.size_;
for (int i = x1.size_ - 1; i >= 0; --i) {
if (x1.arr[i] != x2.arr[i]) return x1.arr[i] < x2.arr[i];
}
return false;
}
friend bool operator>(const bigint& x1, const bigint& x2) {
return x2 < x1;
}
friend bool operator<=(const bigint& x1, const bigint& x2) {
return !(x1 > x2);
}
friend bool operator>=(const bigint& x1, const bigint& x2) {
return !(x1 < x2);
}
friend bool operator==(const bigint& x1, const bigint& x2) {
return !(x1 < x2 || x1 > x2);
}
friend bool operator!=(const bigint& x1, const bigint& x2) {
return x1 < x2 || x1 > x2;
}
friend bigint operator+(const bigint& x1, const bigint& x2) {
bigint res = x1;
res += x2;
return res;
}
friend bigint operator-(const bigint& x1, const bigint& x2) {
bigint res = x1;
return res -= x2;
}
friend bigint operator*(const bigint& x1, const bigint& x2) {
bigint res = x1;
res *= x2;
return res;
}
friend std::istream& operator >> (std::istream& is, bigint& x) {
std::string s;
is >> s;
x = bigint(s);
return is;
}
friend std::ostream& operator<<(std::ostream& os, const bigint& x) {
os << x.to_string();
return os;
}
int binpow(int a, int b, int mod) {
int ret = 1;
while (b) {
if (b & 1) ret = 1LL * ret * a % mod;
a = 1LL * a * a % mod;
b >>= 1;
}
return ret;
}
template <unsigned mod> void fourier_transform(int sz, std::vector<modint<mod> >& f, int primitive_root, bool inverse) {
// O(n log n) Number Theoretic Transform
for (int i = 0, j = 1; j < sz - 1; ++j) {
for (int k = sz >> 1; k >(i ^= k); k >>= 1);
if (i < j) std::swap(f[i], f[j]);
}
modint<mod> root = binpow(primitive_root, (mod - 1) / sz, mod);
std::vector<modint<mod> > pw(sz + 1); pw[0] = 1;
for (int i = 1; i <= sz; i++) pw[i] = pw[i - 1] * root;
for (int b = 1; b < sz; b <<= 1) {
int qs = sz / (b * 2);
for (int i = 0; i < sz; i += b * 2) {
for (int j = i; j < i + b; ++j) {
modint<mod> nf = pw[(inverse ? b * 2 - j + i : j - i) * qs] * f[j + b];
f[j + b] = f[j] - nf;
f[j] += nf;
}
}
}
if (inverse) {
modint<mod> mul = binpow(sz, mod - 2, mod);
for (int i = 0; i < sz; ++i) f[i] *= mul;
}
}
};
#endif
// Refer to http://codeforces.com/blog/entry/14516?#comment-195331
void fibonacci(int n, bigint &x, bigint &y) {
if (n == 0) {
x = 0, y = 1;
return;
}
if (n & 1) {
fibonacci(n - 1, y, x);
y += x;
}
else {
bigint xd, yd;
fibonacci(n >> 1, xd, yd);
bigint zd = xd * xd;
y = zd + yd * yd;
x = 2 * xd * yd - zd;
}
}
int main() {
int n;
std::cin.tie(0);
std::ios_base::sync_with_stdio(false);
std::cin >> n;
std::cout << n << '\n';
bigint x, y;
fibonacci(n, x, y);
if (n & 1) {
std::cout << x << '\n';
}
else {
bigint z;
fibonacci(n >> 1, y, z);
std::cout << x - y * y << '\n';
}
return 0;
}