結果
| 問題 | No.303 割れません |
| ユーザー |
 square1001
|
| 提出日時 | 2020-07-02 16:12:45 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 473 ms / 10,000 ms |
| コード長 | 18,447 bytes |
| コンパイル時間 | 1,646 ms |
| コンパイル使用メモリ | 94,428 KB |
| 実行使用メモリ | 10,500 KB |
| 最終ジャッジ日時 | 2024-09-15 01:06:06 |
| 合計ジャッジ時間 | 6,443 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 226 ms
6,908 KB |
| testcase_04 | AC | 473 ms
10,496 KB |
| testcase_05 | AC | 467 ms
10,244 KB |
| testcase_06 | AC | 472 ms
10,388 KB |
| testcase_07 | AC | 295 ms
10,500 KB |
| testcase_08 | AC | 296 ms
10,496 KB |
| testcase_09 | AC | 291 ms
10,368 KB |
| testcase_10 | AC | 2 ms
5,376 KB |
| testcase_11 | AC | 468 ms
10,496 KB |
| testcase_12 | AC | 299 ms
10,428 KB |
| testcase_13 | AC | 464 ms
10,372 KB |
| testcase_14 | AC | 137 ms
6,784 KB |
| testcase_15 | AC | 109 ms
5,376 KB |
| testcase_16 | AC | 2 ms
5,376 KB |
ソースコード
#ifndef CLASS_MODINT_64321
#define CLASS_MODINT_64321
#include <cassert>
#include <cstdint>
class modint_64321 {
private:
static constexpr std::uint64_t mod = std::uint64_t(1) - (std::uint64_t(1) << 32);
std::uint64_t n;
public:
modint_64321() noexcept : n(0) {};
modint_64321(std::uint64_t n_) noexcept : n(n_ < mod ? n_ : n_ - mod) {};
modint_64321(std::uint32_t n_) noexcept : n(n_) {};
modint_64321(std::int64_t n_) noexcept : n(n_ >= 0 ? n_ : std::uint64_t(n_) + mod) {};
modint_64321(std::int32_t n_) noexcept : n(n_ >= 0 ? n_ : std::uint64_t(n_) + mod) {};
static constexpr std::uint64_t get_mod() noexcept { return mod; }
std::uint64_t get() const noexcept { return n; }
bool operator==(const modint_64321& m) const noexcept { return n == m.n; }
bool operator!=(const modint_64321& m) const noexcept { return n != m.n; }
modint_64321& operator+=(const modint_64321& m) noexcept { n = (n < mod - m.n ? n + m.n : n + m.n - mod); return *this; }
modint_64321& operator-=(const modint_64321& m) noexcept { n = (n >= m.n ? n - m.n : n - m.n + mod); return *this; }
#ifdef __SIZEOF_INT128__
modint_64321& operator*=(const modint_64321& m) noexcept {
__uint128_t g = __int128_t(n) * m.n;
std::uint64_t g0 = g & 4294967295;
std::uint64_t g1 = (g >> 32) & 4294967295;
std::uint64_t g2 = (g >> 64) & 4294967295;
std::uint64_t g3 = (g >> 96);
n = ((g1 + g2) << 32) - (g1 + g2 < 4294967296 ? 0 : mod) + g0 - g2 - g3;
n = (n < mod ? n : (g1 + g2 != 4294967295 ? n + mod : n - mod));
return *this;
}
#else
modint_64321& operator*=(const modint_64321& m) noexcept {
std::uint64_t la = n & 4294967295, lb = (n >> 32);
std::uint64_t ra = m.n & 4294967295, rb = (m.n >> 32);
std::uint64_t g0 = 0, g1 = 0, g2 = 0, g3 = 0;
g0 += la * ra; g1 += (g0 >> 32); g0 &= 4294967295;
g1 += la * rb; g2 += (g1 >> 32); g1 &= 4294967295;
g1 += lb * ra; g2 += (g1 >> 32); g1 &= 4294967295;
g2 += lb * rb; g3 += (g2 >> 32); g2 &= 4294967295;
n = ((g1 + g2) << 32) - (g1 + g2 < 4294967296 ? 0 : mod) + g0 - g2 - g3;
n = (n < mod ? n : (g1 + g2 != 4294967295 ? n + mod : n - mod));
return *this;
}
#endif
modint_64321 operator+(const modint_64321& m) const noexcept { return modint_64321(*this) += m; }
modint_64321 operator-(const modint_64321& m) const noexcept { return modint_64321(*this) -= m; }
modint_64321 operator*(const modint_64321& m) const noexcept { return modint_64321(*this) *= m; }
modint_64321 inv() const {
assert(n != 0);
return pow(mod - 2);
}
modint_64321 pow(std::uint64_t b) const noexcept {
modint_64321 ans(1), m(*this);
while (b) {
if (b & 1) ans *= m;
m *= m;
b >>= 1;
}
return ans;
}
};
#endif // CLASS_MODINT_64321
#ifndef CLASS_POLYNOMIAL_NTT_64321
#define CLASS_POLYNOMIAL_NTT_64321
#include <vector>
#include <algorithm>
class polynomial_ntt_64321 {
public:
using modulo = modint_64321;
private:
static constexpr std::uint64_t primroot = 7;
static constexpr std::uint64_t mod = modulo::get_mod();
public:
static void fourier_transform(std::vector<modulo>& v) {
std::vector<modulo> base_pw(33);
base_pw[32] = modulo(primroot).pow((mod - 1) >> 32);
for (int i = 31; i >= 0; --i) {
base_pw[i] = base_pw[i + 1] * base_pw[i + 1];
}
for (int i = 32; i >= 0; --i) {
base_pw[i] *= modulo(-1);
}
std::size_t s = v.size();
for (std::size_t i = (s >> 1); i >= 1; i >>= 1) {
modulo w(1);
std::size_t cnt = 0;
for (std::size_t j = 0; j < s; j += i * 2) {
for (std::size_t k = j; k < j + i; ++k) {
modulo va(v[k]), vb(v[k + i] * w);
v[k] = va + vb;
v[k + i] = va - vb;
}
w *= base_pw[__builtin_ctz(++cnt) + 2];
}
}
}
static void fourier_transform_inverse(std::vector<modulo>& v) {
std::vector<modulo> base_pw(33);
base_pw[32] = modulo(primroot).pow((mod - 1) - ((mod - 1) >> 32));
for (int i = 31; i >= 0; --i) {
base_pw[i] = base_pw[i + 1] * base_pw[i + 1];
}
for (int i = 32; i >= 0; --i) {
base_pw[i] *= modulo(-1);
}
std::size_t s = v.size();
for (std::size_t i = 1; i < s; i <<= 1) {
modulo w(1);
std::size_t cnt = 0;
for (std::size_t j = 0; j < s; j += i * 2) {
for (std::size_t k = j; k < j + i; ++k) {
modulo va(v[k]), vb(v[k + i]);
v[k] = va + vb;
v[k + i] = (va - vb) * w;
}
w *= base_pw[__builtin_ctz(++cnt) + 2];
}
}
modulo powinv = modulo(s).inv();
for (std::size_t i = 0; i < s; ++i) {
v[i] *= powinv;
}
}
static std::vector<modulo> convolve(std::vector<modulo> v1, std::vector<modulo> v2) {
if (v1.empty() || v2.empty()) {
return std::vector<modulo>();
}
if (v1.size() <= 64 || v2.size() <= 64) {
std::vector<modulo> ans_naive(v1.size() + v2.size() - 1);
for (std::size_t i = 0; i < v1.size(); ++i) {
for (std::size_t j = 0; j < v2.size(); ++j) {
ans_naive[i + j] += v1[i] * v2[j];
}
}
return ans_naive;
}
if (v1.size() < v2.size()) {
swap(v1, v2);
}
std::size_t fsize = v1.size() + v2.size() - 1;
std::size_t step = v2.size();
while (step & (step - 1)) {
step += step & (-step); // step to become minimum 2^k >= v2.size()
}
v1.resize((v1.size() + step - 1) / step * step); // change v1.size() to multiple of step
v2.resize(step * 2);
std::vector<modulo> ans(fsize);
std::vector<modulo> pv1(step * 2);
fourier_transform(v2);
for (std::size_t i = 0; i < v1.size(); i += step) {
std::copy(v1.begin() + i, v1.begin() + i + step, pv1.begin());
std::fill(pv1.begin() + step, pv1.end(), modulo(0));
fourier_transform(pv1);
for (std::size_t j = 0; j < step * 2; ++j) {
pv1[j] *= v2[j];
}
fourier_transform_inverse(pv1);
for (std::size_t j = 0; j < step * 2 && i + j < fsize; ++j) {
ans[j + i] += pv1[j];
}
}
return ans;
}
};
#endif // CLASS_POLYNOMIAL_NTT_64321
#ifndef CLASS_BASICINT
#define CLASS_BASICINT
#include <vector>
#include <cassert>
#include <cstdint>
#include <algorithm>
template<std::uint32_t base>
class basic_int {
// 2 <= base < max(base_type)^(2/3) = 2,642,245
protected:
using base_type = std::uint32_t; // base type
using base_type_d = std::uint64_t; // double of base type
std::size_t capacity;
std::vector<base_type> digit;
void resize(std::size_t capacity_) {
if (capacity != capacity_) {
assert(capacity_ >= 1);
capacity = capacity_;
digit.resize(capacity_);
}
}
void minimize() {
std::size_t d = digits();
while (d & (d - 1)) {
d += d & (-d);
}
resize(d);
}
std::size_t digits() const {
for (std::size_t i = capacity - 1; i >= 1; --i) {
if (digit[i] != 0) {
return i + 1;
}
}
return 1;
}
public:
// ----- #1. Costructors ----- //
explicit basic_int() : capacity(1), digit(1, base_type(0)) {};
explicit basic_int(std::vector<base_type> digit_) : digit(digit_) {
assert(!digit.empty());
for (base_type i : digit) {
assert(0 <= i && i < base);
}
capacity = 1;
while (capacity < digit.size()) {
capacity <<= 1;
}
digit.resize(capacity, 0);
};
// ----- #2. Comparing Operators ----- //
bool operator==(const basic_int& b) const noexcept {
return digit == b.digit;
}
bool operator!=(const basic_int& b) const noexcept {
return digit != b.digit;
}
bool operator<(const basic_int& b) const noexcept {
if (capacity != b.capacity) {
return capacity < b.capacity;
}
for (std::size_t i = capacity - 1; i >= 1; --i) {
if (digit[i] != b.digit[i]) {
return digit[i] < b.digit[i];
}
}
return digit[0] < b.digit[0];
}
bool operator>(const basic_int& b) const noexcept {
if (capacity != b.capacity) {
return capacity > b.capacity;
}
for (std::size_t i = capacity - 1; i >= 1; --i) {
if (digit[i] != b.digit[i]) {
return digit[i] > b.digit[i];
}
}
return digit[0] > b.digit[0];
}
bool operator<=(const basic_int& b) const noexcept {
return basic_int(*this) < b || basic_int(*this) == b;
}
bool operator>=(const basic_int& b) const noexcept {
return basic_int(*this) > b || basic_int(*this) == b;
}
// ----- #3. Shifting ----- //
basic_int& operator<<=(std::size_t s) noexcept {
std::size_t d = digits();
if (d + s > capacity) {
std::size_t nxtcap = d + s;
while (nxtcap & (nxtcap - 1)) {
nxtcap += nxtcap & (-nxtcap);
}
resize(nxtcap);
}
for (std::size_t i = d - 1; i != std::size_t(-1); --i) {
digit[i + s] = digit[i];
}
std::fill(digit.begin(), digit.begin() + s, 0);
return *this;
}
basic_int& operator>>=(std::size_t s) noexcept {
std::size_t d = digits();
if (d <= s) {
(*this) = basic_int();
}
else {
for (std::size_t i = 0; i < d - s; ++i) {
digit[i] = digit[i + s];
}
std::fill(digit.begin() + d - s, digit.begin() + d, 0);
minimize();
}
return *this;
}
// ----- #4. Addition ----- //
basic_int& operator+=(const basic_int& b) {
resize(std::max(capacity, b.capacity));
bool carry = false;
for (std::uint32_t i = 0; i < b.capacity; ++i) {
digit[i] += b.digit[i] + (carry ? 1 : 0);
carry = (digit[i] >= base);
if (carry) digit[i] -= base;
}
for (std::uint32_t i = b.capacity; i < capacity; ++i) {
digit[i] += (carry ? 1 : 0);
carry = (digit[i] >= base);
if (carry) digit[i] -= base;
}
if (carry) {
resize(capacity << 1);
digit[capacity >> 1] = 1;
}
return *this;
}
// ----- #5. Subtraction ----- //
basic_int& operator-=(const basic_int& b) {
bool carry = false;
for (std::uint32_t i = 0; i < b.capacity; ++i) {
digit[i] += base - b.digit[i] - (carry ? 1 : 0);
carry = (digit[i] < base);
if (!carry) digit[i] -= base;
}
for (std::uint32_t i = b.capacity; i < capacity; ++i) {
digit[i] += base - (carry ? 1 : 0);
carry = (digit[i] < base);
if (!carry) digit[i] -= base;
}
// assert(!carry) // noexcept
minimize();
return *this;
}
// ----- #6. Multiplication ----- //
basic_int& operator*=(const basic_int& b) {
using ntt = polynomial_ntt_64321;
std::size_t nxtcap = std::max(capacity, b.capacity) * 2;
std::vector<ntt::modulo> nxtdigit = ntt::convolve(std::vector<ntt::modulo>(digit.begin(), digit.end()), std::vector<ntt::modulo>(b.digit.begin(), b.digit.end()));
nxtdigit.resize(nxtcap);
capacity = nxtcap;
digit = std::vector<std::uint32_t>(capacity, 0);
std::uint64_t carry = 0;
for (std::uint32_t i = 0; i < capacity; ++i) {
std::uint64_t nxt = nxtdigit[i].get() + carry;
carry = nxt / base;
digit[i] = nxt - carry * base;
}
minimize();
return *this;
}
// ----- #7. Division ----- //
basic_int& operator/=(const basic_int& b) {
assert(b != basic_int());
if ((*this) < b) {
(*this) = basic_int();
}
else {
std::size_t digit_a = digits();
std::size_t digit_b = b.digits();
std::size_t req_precis = digit_a - digit_b + 2;
std::size_t set_precis = 1;
while (set_precis < req_precis) set_precis <<= 1;
// Find the inverse!
std::uint64_t gen = (digit_b == 1 ? std::uint64_t(b.digit[0]) * base : std::uint64_t(b.digit[digit_b - 1]) * base + b.digit[digit_b - 2]);
std::uint64_t gen_inv = std::uint64_t(base) * base * base / (gen + 1);
std::size_t current_precis = 2;
basic_int inv({ std::uint32_t(gen_inv % base), std::uint32_t(gen_inv / base) });
while (current_precis < set_precis) {
std::size_t digit_nb = std::min(digit_b, current_precis * 2);
basic_int nb = (digit_b == digit_nb ? b : b >> (digit_b - digit_nb));
inv = (((basic_int({ 2 }) << (current_precis + digit_nb - 1)) - inv * nb - basic_int({ 1 })) * inv) >> (digit_nb - 1);
current_precis *= 2;
}
while (true) {
basic_int next_inv = (((basic_int({ 2 }) << (current_precis + digit_b - 1)) - inv * b - basic_int({ 1 })) * inv) >> (set_precis + digit_b - 1);
if (inv == next_inv) break;
inv = next_inv;
}
basic_int val = (basic_int(*this) * inv) >> (set_precis + digit_b - 1);
while (b * (val + basic_int({ 1 })) <= (*this)) {
val += basic_int({ 1 });
}
(*this) = val;
}
return *this;
}
// ----- #8. Operators ----- //
basic_int operator<<(std::size_t s) const { return basic_int(*this) <<= s; }
basic_int operator>>(std::size_t s) const { return basic_int(*this) >>= s; }
basic_int operator+(const basic_int& b) const { return basic_int(*this) += b; }
basic_int operator-(const basic_int& b) const { return basic_int(*this) -= b; }
basic_int operator*(const basic_int& b) const { return basic_int(*this) *= b; }
basic_int operator/(const basic_int& b) const { return basic_int(*this) /= b; }
};
#endif // CLASS_BASICINT
#ifndef CLASS_BIGINT
#define CLASS_BIGINT
#include <string>
#include <iostream>
// (digit / base_digit) * base_number^2 <= 2^64 - 2^32 + 1 = 18446744069414584321
// (digit / base_digit) < min(2^27, 2^26) = 67108864
// ---> max_digit = min(92233720, 335544320) = 92233720
constexpr std::size_t base_digit = 6;
constexpr std::uint32_t base_number = 1000000;
class bigint : private basic_int<base_number> {
private:
bool sign; // positive/zero = false, negative = true
bool is_number(std::string str) {
if(str.empty() || str == "-" || !(('0' <= str[0] && str[0] <= '9') || str[0] == '-')) {
return false;
}
for(std::uint64_t i = 1; i < str.size(); ++i) {
if(!('0' <= str[i] && str[i] <= '9')) {
return false;
}
}
return true;
}
std::vector<std::uint32_t> to_basic_expression(std::uint64_t x) {
std::vector<std::uint32_t> res;
do {
res.push_back(x % base_number);
x /= base_number;
} while(x != 0);
return res;
}
public:
// ----- #1. Constructors / String Functions ----- //
bigint() : basic_int(), sign(false) {};
bigint(std::int64_t x) : basic_int(to_basic_expression(x >= 0 ? x : -x)), sign(x < 0) {};
bigint(const std::string& str) {
assert(is_number(str));
sign = (str[0] == '-');
std::size_t initial = (sign ? 1 : 0);
while(initial + 1 != str.size() && str[initial] == '0') {
++initial;
}
std::size_t str_digits = str.size() - initial;
capacity = 1;
while(capacity * base_digit < str_digits) {
capacity *= 2;
}
digit = std::vector<std::uint32_t>(capacity, 0);
for(std::size_t i = 0; (i + 1) * base_digit < str_digits; ++i) {
digit[i] = std::stoi(str.substr(str.size() - i * base_digit - base_digit, base_digit));
}
digit[(str_digits - 1) / base_digit] = std::stoi(str.substr(initial, (str.size() - (str_digits - 1) / base_digit * base_digit) - initial));
}
std::string to_string() const {
std::size_t d = digits();
std::string res = (sign ? "-" : "") + std::to_string(digit[d - 1]);
for(std::size_t i = d - 2; i != std::size_t(-1); --i) {
std::string digit_str = std::to_string(digit[i]);
res += std::string(base_digit - digit_str.size(), '0') + digit_str;
}
return res;
}
// ----- #2. Operators ----- //
bool operator==(const bigint& b) const noexcept { return sign == b.sign && basic_int::operator==(b); }
bool operator!=(const bigint& b) const noexcept { return sign != b.sign || basic_int::operator!=(b); }
bool operator<(const bigint& b) const noexcept { return sign != b.sign ? sign : basic_int::operator<(b); }
bool operator>(const bigint& b) const noexcept { return sign != b.sign ? !sign : basic_int::operator>(b); }
bool operator<=(const bigint& b) const noexcept { return sign != b.sign ? sign : basic_int::operator<=(b); }
bool operator>=(const bigint& b) const noexcept { return sign != b.sign ? !sign : basic_int::operator>=(b); }
bigint& operator+=(const bigint& b) {
if(sign == b.sign) {
basic_int::operator+=(b);
}
else if(basic_int(*this) >= basic_int(b)) {
basic_int::operator-=(b);
if(sign && basic_int(*this) == basic_int()) sign = false;
}
else {
sign = !sign;
(*this) = b - (*this);
}
return *this;
}
bigint& operator-=(const bigint& b) {
if(sign != b.sign) {
basic_int::operator+=(b);
}
else if(basic_int(*this) >= basic_int(b)) {
basic_int::operator-=(b);
if(sign && basic_int(*this) == basic_int()) sign = false;
}
else {
sign = !sign;
(*this) += b;
sign = !sign;
}
return *this;
}
bigint& operator*=(const bigint& b) {
basic_int::operator*=(b);
if(b.sign) sign = !sign;
if(sign && basic_int(*this) == basic_int()) sign = false;
return *this;
}
bigint& operator/=(const bigint& b) {
basic_int::operator/=(b);
if(b.sign) sign = !sign;
if(sign && basic_int(*this) == basic_int()) sign = false;
return *this;
}
bigint operator%=(const bigint& b) {
bigint itself(*this);
(*this) = itself - itself / b * b;
return *this;
}
bigint operator+(const bigint& b) const { return bigint(*this) += b; }
bigint operator-(const bigint& b) const { return bigint(*this) -= b; }
bigint operator*(const bigint& b) const { return bigint(*this) *= b; }
bigint operator/(const bigint& b) const { return bigint(*this) /= b; }
bigint operator%(const bigint& b) const { return bigint(*this) %= b; }
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; }
};
#endif // CLASS_BIGINT
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 = xd * yd * 2 - zd;
}
}
int main() {
int n;
std::cin.tie(0);
std::ios_base::sync_with_stdio(false);
std::cin >> n;
if(n == 2) {
std::cout << 3 << '\n';
std::cout << "INF\n";
}
else {
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;
}