結果

問題 No.303 割れません
ユーザー square1001
提出日時 2022-08-20 13:46:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 245 ms / 10,000 ms
コード長 15,655 bytes
コンパイル時間 1,706 ms
コンパイル使用メモリ 94,268 KB
実行使用メモリ 19,604 KB
最終ジャッジ日時 2024-10-09 06:40:37
合計ジャッジ時間 4,589 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize("O3")
#ifndef NAMESPACE_CONVOLUTION
#define NAMESPACE_CONVOLUTION
#include <cstdint>
#include <algorithm>
namespace convolution {
    /*
        MODINT CLASS FOR DOING NUMBER THEORETIC TRANSFORM (NTT)
        - arrays of 4 different mod-integers
        - works well with compiler option -O3, because it optimizes for MOD[i] = a * 2^k + 1 for small a
          * MOD[i]: mod values
          * GARNER[i]: equals MOD[s]^-1 (mod MOD[t]), for (s, t) = (0, 1), (0, 2), (1, 2), (0, 3), (1, 3), (2, 3)
        
        BENCHMARK (2022.8.19)
        - AtCoder: 4.148 seconds for 10^9 multiplications with -O3
        - ideone.com: 3.204 seconds for 5*10^8 multiplications with -O3
    */
    class ntt_modint {
    public:
        alignas(32) std::int64_t x[4];
        alignas(32) static constexpr std::int64_t MOD[4] = {
            (51LL << 25) + 1LL, (54LL << 25) + 1LL, (60LL << 25) + 1LL, (63LL << 25) + 1LL
        };
        alignas(32) static constexpr std::int64_t GARNER[6] = {
            18LL,
            (5LL << 27) + 7LL, 10LL,
            (189LL << 23) + 6LL, 7LL, 21LL
        };
        explicit ntt_modint() {
            x[0] = 0LL; x[1] = 0LL; x[2] = 0LL; x[3] = 0LL;
        }
        explicit ntt_modint(std::int64_t x0_, std::int64_t x1_, std::int64_t x2_, std::int64_t x3_) {
            x[0] = x0_; x[1] = x1_; x[2] = x2_; x[3] = x3_;
            for (int i = 0; i < 4; i++) {
                x[i] = (x[i] >= 0 ? x[i] % MOD[i] : (MOD[i] - (-x[i] % MOD[i]))) % MOD[i];
            }
        }
        ntt_modint& operator+=(const ntt_modint& m) {
            for (int i = 0; i < 4; i++) {
                x[i] += m.x[i];
                x[i] -= (x[i] >= MOD[i] ? MOD[i] : 0LL);
            }
            return (*this);
        }
        ntt_modint& operator-=(const ntt_modint& m) {
            for (int i = 0; i < 4; i++) {
                x[i] -= m.x[i];
                x[i] += (x[i] < 0LL ? MOD[i] : 0LL);
            }
            return (*this);
        }
        ntt_modint& operator*=(const ntt_modint& m) {
            for (int i = 0; i < 4; i++) {
                x[i] = x[i] * m.x[i] % MOD[i];
            }
            return (*this);
        }
        ntt_modint operator+(const ntt_modint& m) const {
            return ntt_modint(*this) += m;
        }
        ntt_modint operator-(const ntt_modint& m) const {
            return ntt_modint(*this) -= m;
        }
        ntt_modint operator*(const ntt_modint& m) const {
            return ntt_modint(*this) *= m;
        }
        __int128_t get() const {
            std::int64_t v[4];
            int idx = 0;
            for (int i = 0; i < 4; i++) {
                v[i] = x[i];
                for (int j = 0; j < i; j++) {
                    v[i] = GARNER[idx++] * (v[i] - v[j] + MOD[i]) % MOD[i];
                }
            }
            __int128_t res = v[0];
            __int128_t mul = 1;
            for (int i = 0; i < 3; i++) {
                mul *= MOD[i];
                res += v[i + 1] * mul;
            }
            return res;
        }
    };
    constexpr std::int64_t ntt_modint::MOD[4];
    constexpr std::int64_t ntt_modint::GARNER[6];
    
    /*
        FUNCTION FOR NUMBER-THEORETIC TRANSFORM - FORWARD DIRECTION
        - do NTT in forward direction for an array x of size (1 << level)
    */
    void forward_ntt(int level, ntt_modint* x) {
        ntt_modint f[25];
        f[23] = ntt_modint(40, 103, 170, 551); // 2^25-th root for each mod (note: 23 = 25 - 2)
        for (int i = 22; i >= 0; i--) {
            f[i] = f[i + 1] * f[i + 1];
        }
        for (int i = 0; i <= 23; i++) {
            f[i] *= ntt_modint(-1, -1, -1, -1);
        }
        int s = (1 << level);
        for (int i = level - 1; i >= 0; i--) {
            ntt_modint mult(1, 1, 1, 1);
            for (int j = 0; j < s; j += (2 << i)) {
                for (int k = j; k < j + (1 << i); k++) {
                    ntt_modint xl = x[k];
                    ntt_modint xr = x[k + (1 << i)];
                    x[k] = xl + mult * xr;
                    x[k + (1 << i)] = xl - mult * xr;
                }
                mult *= f[__builtin_ctz(~(j >> (i + 1)))];
            }
        }
    }
    
    /*
        FUNCTION FOR NUMBER-THEORETIC TRANSFORM - REVERSE DIRECTION
        - do NTT in reverse direction for an array x of size (1 << level)
    */
    void reverse_ntt(int level, ntt_modint* x) {
        ntt_modint f[25];
        f[23] = ntt_modint(983983719, 1213823434, 698721702, 1392661172); // inverse of 2^25-th root for each mod (note: 23 = 25 - 2)
        for (int i = 22; i >= 0; i--) {
            f[i] = f[i + 1] * f[i + 1];
        }
        for (int i = 0; i <= 23; i++) {
            f[i] *= ntt_modint(-1, -1, -1, -1);
        }
        int s = (1 << level);
        for (int i = 0; i < level; i++) {
            ntt_modint mult(1, 1, 1, 1);
            for (int j = 0; j < s; j += (2 << i)) {
                for (int k = j; k < j + (1 << i); k++) {
                    ntt_modint xl = x[k];
                    ntt_modint xr = x[k + (1 << i)];
                    x[k] = xl + xr;
                    x[k + (1 << i)] = (xl - xr) * mult;
                }
                mult *= f[__builtin_ctz(~(j >> (i + 1)))];
            }
        }
        ntt_modint inv2 = ntt_modint((ntt_modint::MOD[0] + 1) / 2, (ntt_modint::MOD[1] + 1) / 2, (ntt_modint::MOD[2] + 1) / 2, (ntt_modint::MOD[3] + 
            1) / 2);
        ntt_modint powinv(1, 1, 1, 1);
        for (int i = 0; i < level; i++) {
            powinv *= inv2;
        }
        for (int i = 0; i < s; i++) {
            x[i] *= powinv;
        }
    }
    
    /*
        FUNCTION FOR CONVOLUTION
        - convolves two arrays a and b, and returns the output in array c
          * sa = (size of array a)
          * sb = (size of array b)
          * outputs the array c of size sa+sb-1
        - works for 0 <= c[i] < 13196394894239664472536019622531432449 (~ 1.32 * 10^37)
    */
    void convolve(int sa, int sb, std::int64_t *a, std::int64_t *b, __int128_t *c) {
        if (sa < sb) {
            std::swap(sa, sb);
            std::swap(a, b);
        }
        if (sb <= 48) {
            ntt_modint *va = new ntt_modint[sa];
            ntt_modint *vb = new ntt_modint[sb];
            ntt_modint *vc = new ntt_modint[sa + sb - 1];
            for (int i = 0; i < sa; i++) {
                va[i] = ntt_modint(a[i], a[i], a[i], a[i]);
            }
            for (int i = 0; i < sb; i++) {
                vb[i] = ntt_modint(b[i], b[i], b[i], b[i]);
            }
            for (int i = 0; i < sa; i++) {
                for (int j = 0; j < sb; j++) {
                    vc[i + j] += va[i] * vb[j];
                }
            }
            for (int i = 0; i < sa + sb - 1; i++) {
                c[i] = vc[i].get();
            }
            delete[] va;
            delete[] vb;
            delete[] vc;
        }
        else {
            for (int i = 0; i < sa + sb - 1; i++) {
                c[i] = 0;
            }
            int level = 0;
            while ((1 << level) < sb) {
                level += 1;
            }
            ntt_modint *va = new ntt_modint[2 << level];
            ntt_modint *vb = new ntt_modint[2 << level];
            for (int i = 0; i < sb; i++) {
                vb[i] = ntt_modint(b[i], b[i], b[i], b[i]);
            }
            forward_ntt(level + 1, vb);
            for (int i = 0; i < sa; i += (1 << level)) {
                int limit = std::min(sa - i, 1 << level);
                for (int j = 0; j < limit; j++) {
                    va[j] = ntt_modint(a[i + j], a[i + j], a[i + j], a[i + j]);
                }
                for (int j = limit; j < (2 << level); j++) {
                    va[j] = ntt_modint();
                }
                forward_ntt(level + 1, va);
                for (int j = 0; j < (2 << level); j++) {
                    va[j] *= vb[j];
                }
                reverse_ntt(level + 1, va);
                for (int j = 0; j < limit + sb - 1; j++) {
                    c[i + j] += va[j].get();
                }
            }
            delete[] va;
            delete[] vb;
        }
    }
}
#endif // NAMESPACE_CONVOLUTION
#ifndef CLASS_BASIC_INTEGER
#define CLASS_BASIC_INTEGER
#include <cstdint>
#include <algorithm>
class basic_integer {
public:
    static constexpr int BASE_DIGITS = 14;
    static constexpr std::int64_t BASE = 100'000'000'000'000LL;
    int size_;
    int capacity_;
    std::int64_t *x;
    // constructor #1: default constructor, set value = 0
    basic_integer() : size_(1), capacity_(1) {
        x = new std::int64_t[1];
        x[0] = std::int64_t(0);
    }
    // constructor #2: copy constructor
    basic_integer(const basic_integer& b) : size_(b.size_), capacity_(b.capacity_) {
        x = new std::int64_t[capacity_];
        for (int i = 0; i < capacity_; i++) {
            x[i] = b.x[i];
        }
    }
    // copy operator
    basic_integer& operator=(const basic_integer& b) {
        size_ = b.size_;
        capacity_ = b.capacity_;
        delete[] x;
        x = new std::int64_t[capacity_];
        for (int i = 0; i < capacity_; i++) {
            x[i] = b.x[i];
        }
        return (*this);
    }
    // destructor
    ~basic_integer() {
        delete[] x;
    }
    // root function #1: change capacity
    void change_capacity(int new_capacity_) {
        if (capacity_ == new_capacity_) {
            return;
        }
        int limit = std::min(capacity_, new_capacity_);
        std::int64_t *tx = new std::int64_t[limit];
        for (int i = 0; i < limit; i++) {
            tx[i] = x[i];
        }
        delete[] x;
        x = new std::int64_t[new_capacity_];
        for (int i = 0; i < limit; i++) {
            x[i] = tx[i];
        }
        delete[] tx;
        for (int i = limit; i < new_capacity_; i++) {
            x[i] = 0LL;
        }
        capacity_ = new_capacity_;
    }
    // root function #2: digits(), returns the number of digits
    int digits() const {
        std::int64_t v = x[size_ - 1];
        int digit = 0;
        do {
            digit += 1;
            v /= 10;
        } while (v != 0LL);
        return digit + (size_ - 1) * BASE_DIGITS;
    }
    // root function #3. comparison function
    int compare(const basic_integer& b) const {
        // if self < b, returns -1
        // if self == b, returns 0
        // if self > b, returns +1
        if (size_ != b.size_) {
            return (size_ < b.size_ ? -1 : +1);
        }
        for (int i = size_ - 1; i >= 0; i--) {
            if (x[i] != b.x[i]) {
                return (x[i] < b.x[i] ? -1 : +1);
            }
        }
        return 0;
    }
    // operator #1. += operator
    basic_integer& operator+=(const basic_integer& b) {
        change_capacity(std::max(capacity_, b.capacity_));
        for (int i = 0; i < b.size_; i++) {
            x[i] += b.x[i];
        }
        size_ = std::max(size_, b.size_);
        for (int i = 0; i < size_ - 1; i++) {
            if (x[i] >= BASE) {
                x[i] -= BASE;
                x[i + 1] += 1;
            }
            else if (i >= b.size_) {
                break;
            }
        }
        if (x[size_ - 1] >= BASE) {
            if (size_ == capacity_) {
                change_capacity(capacity_ * 2);
            }
            x[size_ - 1] -= BASE;
            x[size_] += 1;
            size_ += 1;
        }
        return (*this);
    }
    // operator #2. -= operator
    basic_integer& operator-=(const basic_integer& b) {
        for (int i = 0; i < b.size_; i++) {
            x[i] -= b.x[i];
        }
        for (int i = 0; i < size_; i++) {
            if (x[i] < 0) {
                x[i] += BASE;
                x[i + 1] -= 1;
            }
            else if (i >= b.size_) {
                break;
            }
        }
        while (size_ >= 2 && x[size_ - 1] == 0) {
            size_ -= 1;
        }
        int new_capacity_ = capacity_;
        while (size_ <= new_capacity_ / 2) {
            new_capacity_ /= 2;
        }
        change_capacity(new_capacity_);
        return (*this);
    }
    // operator #3. *= operator
    basic_integer& operator*=(const basic_integer& b) {
        __int128_t *c = new __int128_t[size_ + b.size_ - 1];
        convolution::convolve(size_, b.size_, x, b.x, c);
        int new_size_ = size_ + b.size_;
        int new_capacity_ = std::max(capacity_, b.capacity_);
        if (new_size_ > new_capacity_) {
            new_capacity_ *= 2;
        }
        change_capacity(new_capacity_);
        __int128_t carry = 0;
        for (int i = 0; i < size_ + b.size_ - 1; i++) {
            carry += c[i];
            x[i] = carry % BASE;
            carry /= BASE;
        }
        x[size_ + b.size_ - 1] = carry;
        while (new_size_ >= 2 && x[new_size_ - 1] == 0) {
            new_size_ -= 1;
        }
        size_ = new_size_;
        while (size_ <= new_capacity_ / 2) {
            new_capacity_ /= 2;
        }
        change_capacity(new_capacity_);
        return (*this);
    }
};
#endif // CLASS_BASIC_INTEGER
#ifndef CLASS_BIG_INTEGER
#define CLASS_BIG_INTEGER
#include <string>
#include <algorithm>
#include <stdexcept>
class big_integer {
private:
    basic_integer content;
    bool negative;
public:
    big_integer() : content(basic_integer()), negative(false) {};
    // constructor by string (e.g. "123", "4567", "0089", "0")
    big_integer(const std::string& s) {
        // check the validity
        if (!(s != "" && (('0' <= s[0] && s[0] <= '9') || s[0] == '-'))) {
            throw std::invalid_argument("big_integer: string does not represent an integer");
        }
        int l = (s[0] != '-' ? 0 : 1);
        for (int i = l; i < int(s.size()); i++) {
            if (!('0' <= s[i] && s[i] <= '9')) {
                throw std::invalid_argument("big_integer: string does not represent an integer");
            }
        }
        while (s[l] == '0' && l != int(s.size()) - 1) {
            l += 1;
        }
        content.size_ = (int(s.size()) - l + basic_integer::BASE_DIGITS - 1) / basic_integer::BASE_DIGITS;
        content.capacity_ = 1;
        while (content.capacity_ < content.size_) {
            content.capacity_ <<= 1;
        }
        content.x = new std::int64_t[content.capacity_];
        for (int i = 0; i < content.capacity_; i++) {
            content.x[i] = 0LL;
        }
        for (int i = l; i < int(s.size()); i++) {
            int pos = (int(s.size()) - i - 1) / basic_integer::BASE_DIGITS;
            content.x[pos] = content.x[pos] * 10 + int(s[i] - '0');
        }
        negative = (s[0] == '-' && (content.size_ >= 2 || content.x[0] != 0LL) ? true : false);
    }
    // to_string() : convert integer to string
    std::string to_string() const {
        int digit = content.digits();
        std::string res(digit + (negative ? 1 : 0), '?');
        if (negative) {
            res[0] = '-';
        }
        for (int i = 0; i < content.size_; i++) {
            std::int64_t v = content.x[i];
            int limit = std::min(basic_integer::BASE_DIGITS * (i + 1), digit);
            for (int j = basic_integer::BASE_DIGITS * i; j < limit; j++) {
                res[digit - j - (negative ? 0 : 1)] = char(v % 10 + '0');
                v /= 10;
            }
        }
        return res;
    }
    // digits() : returns the number of digits
    int digits() const {
        return content.digits();
    }
    // comparison operator #1. == operator
    bool operator==(const big_integer& b) const {
        return (negative == b.negative && content.compare(b.content) == 0);
    }
    // comparison operator #2. != operator
    bool operator!=(const big_integer& b) const {
        return (negative != b.negative || content.compare(b.content) != 0);
    }
    // comparison operator #3. < operator
    bool operator<(const big_integer& b) const {
        return (negative == b.negative ? content.compare(b.content) == -1 : negative);
    }
    // comparison operator #4. > operator
    bool operator>(const big_integer& b) const {
        return (negative == b.negative ? content.compare(b.content) == +1 : b.negative);
    }
    // comparison operator #5. <= operator
    bool operator<=(const big_integer& b) const {
        return (negative == b.negative ? content.compare(b.content) != +1 : negative);
    }
    // comparison operator #6. >= operator
    bool operator>=(const big_integer& b) const {
        return (negative == b.negative ? content.compare(b.content) != -1 : b.negative);
    }
    // operator A1. += operator
    big_integer& operator+=(const big_integer& b) {
        if (negative == b.negative) {
            content += b.content;
        }
        else if (content.compare(b.content) == -1) {
            content = (basic_integer(b.content) -= content);
            negative = !negative;
        }
        else {
            content -= b.content;
            if (negative && content.size_ == 1 && content.x[0] == 0) {
                negative = false;
            }
        }
        return (*this);
    }
    // operator A2. -= operator
    big_integer& operator-=(const big_integer& b) {
        if (negative != b.negative) {
            content += b.content;
        }
        else if (content.compare(b.content) == -1) {
            content = (basic_integer(b.content) -= content);
            negative = !negative;
        }
        else {
            content -= b.content;
            if (negative && content.size_ == 1 && content.x[0] == 0) {
                negative = false;
            }
        }
        return (*this);
    }
    // operator A3. *= operator
    big_integer& operator*=(const big_integer& b) {
        content *= b.content;
        negative = (negative ? !b.negative : b.negative);
        if (negative && content.size_ == 1 && content.x[0] == 0) {
            negative = false;
        }
        return (*this);
    }
    // operator B1. + operator
    big_integer operator+(const big_integer& b) const {
        return big_integer(*this) += b;
    }
    // operator B2. - operator
    big_integer operator-(const big_integer& b) const {
        return big_integer(*this) -= b;
    }
    // operator B3. * operator
    big_integer operator*(const big_integer& b) const {
        return big_integer(*this) *= b;
    }
};
#endif
#include <iostream>
void fibonacci(int n, big_integer &x, big_integer &y) {
    if (n == 0) {
        x = big_integer("0"), y = big_integer("1");
        return;
    }
    if (n & 1) {
        fibonacci(n - 1, y, x);
        y += x;
    }
    else {
        big_integer xd, yd;
        fibonacci(n >> 1, xd, yd);
        big_integer zd = xd * xd;
        y = zd + yd * yd;
        x = xd * yd * big_integer("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';
        big_integer x, y;
        fibonacci(n, x, y);
        if (n & 1) {
            std::cout << x.to_string() << '\n';
        }
        else {
            big_integer z;
            fibonacci(n >> 1, y, z);
            std::cout << (x - y * y).to_string() << '\n';
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0